有序的，线性的，仿射的，还是相关的？

Question

背景

补充阅读1，补充阅读2

线性λ演算是lambda演算的一种有限形式，其中每一个定界变量都必须精确地使用一次。例如，\a b c d e -> a b (d c) e是线性lambda演算中的一个有效项。当作为一个逻辑系统嵌入时，这将强制每个输入被精确地消耗一次。逻辑/类型/语言理论中的等价物分别称为线性逻辑、线性类型和线性语言。

有序lambda微积分是一个更有限的版本:它要求变量按照引入的顺序使用。\a b c d e -> a (b c) (d e)就是这样一个例子。

仿射和相关的lambda结石是线性lambda结石的松弛版本。

• 仿射:每个变量最多只能使用一次。\a b c d e -> a (d c) e
• 相关:每个变量必须至少使用一次。\a b c d -> a (c b) (d c)

如果省略和复制变量都是允许的，我们就得到简单的lambda微积分。

它们与BCKW组合子微积分有着有趣的关系：

• 有序λ微积分可以用B和I组合子来表示。(我需要代表\a -> a)a b c d e -> a (B c) a c d -> B (a (B c)) d b c -> B (a (B c)) a b -> B B (B A B) a -> B (B b) (b (b B)) B (b (B B))B
• 线性λ演算可以用B和C组合子表示。A b c d e -> a b (d c) a b c d -> a b (d c) a c -> B (a B) (C c) a b -> B (B (a b)) (C I) a -> C (B B (B B a)) (C (B (B b) (B B) (C I)
• 仿射λ演算可以用BCK表示。K允许删除未使用的变量。A、b c d e -> a (d c) e b c d -> a (d c) a c -> B a (C I c) a b -> B (B a) (C I) a -> K (B (B a) (C I)) B K (C (B B B) (C I))
• 相关的lambda演算可以用BCW表示。W允许复制变量。A b c d -> a (C b) a c -> B (a (C b)) (a (C b)) a b -> W (\c1 c2 -> B (a (c1 B)) (c I C2)a b -> W (\c1 -> B (B (a (c1 B) (C I)) a b -> W (C (B B (B B (B A) (C I).
• BCKW构成了平原蓝宝石的完整基础。

挑战

给定以下格式的lambda术语，将其分为五个类别中的一个(有序、线性、仿射、相关、无关联)。输出应该是输入所属的最具限制性的输出。

输入是一个lambda术语，它以一个或多个术语作为输入，并以某种方式组合它们，就像上面使用的所有示例一样。为了简化，我们可以消除输入变量的列表，只需使用变量的数量和“函数体”，其中使用的每个变量都被编码为参数列表中的索引。\a b c d e -> a b (d c) e被编码为5, "1 2 (4 3) 5"。(请注意，它不同于de索引。)

函数体可以看作是整数的字符串或嵌套结构。“变量索引”可以是基于0或1的索引，您需要处理10或更高的索引。

对于输出，您可以选择五个一致的值来表示这五个类别中的每一个。

适用标准的密码-高尔夫规则。以字节为单位的最短代码获胜。

测试用例

length, "body" (lambda term it represents) => answer

1, "1" (\a -> a) => Ordered
2, "1 2" (\a b -> a b) => Ordered
2, "2 1" (\a b -> b a) => Linear
2, "1" (\a b -> a) => Affine
2, "2 (1 2)" (\a b -> b (a b)) => Relevant
2, "1 1" (\a b -> a a) => None
3, "1 3 (2 3)" (\a b c -> a c (b c)) => Relevant
4, "1 3 (2 3)" (\a b c d -> a c (b c)) => None
10, "1 (2 (3 4) 5) 6 7 8 (9 10)" => Ordered
10, "5 (2 (6 10) 1) 3 7 8 (9 4)" => Linear
10, "5 (2 (6 10) 1) (9 4)" => Affine
10, "1 5 (2 (3 6 10) 1) 3 7 8 (10 9 4)" => Relevant
10, "1 (2 (4 10) 1) 5 (9 4)" => None

Answer 1

JavaScript，71字节

a=>g=i=>i&&(h=j=>~a.flat(1/0).indexOf(i,-j),h(p=h())?5:p?i<-p:3)|g(i-1)

在网上试试！

输入嵌套整数数组(1-索引)和操作数。假设输入始终有效。输出一个数字。

• 0-有序
• 1-线性
• 3-仿射
• 5-相关
• 7-无

Answer 2

R >= 4.1，81字节

\(x,n)identical(u<-unlist(x,T),r<-1:n+0)+pmin(1:2,range(sapply(r,\(y)sum(u==y))))

在网上试试！

一个函数，它接受整数的嵌套列表x和参数n的数量。返回长度为2的向量：

[0,1] - Affine
[0,2] - None
[1,1] - Linear
[1,2] - Relevant
[2,2] - Ordered

Answer 3

木炭，38字节

≔Ｉ⪪ΦＳ›@ι θ≔ＥＮ№θιη¿⁼θＥηκO¿⁼¹⌈η§AL⌊η¿⌊ηR

在网上试试！链接是详细的代码版本。将字符串(带有[]分隔符)作为第一个输入，将0索引变量的数目作为第二个输入。解释：

≔Ｉ⪪ΦＳ›@ι θ

输入字符串，过滤掉[]s，在空格上拆分，然后转换为整数。

≔ＥＮ№θιη

计算每个变量出现的次数。

¿⁼θＥηκO

如果扁平的术语列表等于变量列表，则输出O，否则.

¿⁼¹⌈η§AL⌊η

..。如果每个变量最多只有一个变量，则输出L (至少)每个变量中的一个，如果至少缺少一个变量，则输出A，否则.

¿⌊ηR

..。如果每个变量中至少有一个，则输出R，否则不输出任何变量。