如何使用 lambda 演算编写一个函数来检查数组的对称性？

Question

我正在学习 Lambda 微积分。我需要根据输入数组是否从中心对称来定义 returns true 或 false 的辛迪加 lambda 图像。我会很高兴得到你的帮助，因为这个话题对我来说很难。我了解如何定义基本构造函数，例如 true 或 false，以及加法和乘法。我有一些算法，正如我想做的那样：

求出栈中元素的个数。
将堆栈的一半（向下舍入）拉到另一个堆栈上。
如果元素个数为奇数，则从第一个栈中移除该元素。
成对地，从栈中取出元素并比较，如果不相等，return构造函数为假，如果栈为空，return构造函数为真。

更新

1.lenght = λl.l (λx.succ), 其中succ = λnfx.n f (f x)

Answer 1

在纯 λ 演算中，您无法访问任何数据类型，但您仍然可以使用所谓的 Church 编码来表示它们。

例如，一元表示的自然数可以是0（z）或另一个自然数n的后继（s），即, 代表 n+1。所以你有 z、s z、s (s z)、s (s (s z)) 等。为了在 λ 演算中表示它们，您使用以 z 和 s 作为参数的函数： λz.λs.z、λz.λs.s z、λz.λs.s (s z)、λz.λs.s (s (s z)) 等

这种表示的妙处在于，它还为您提供了自然数的递归，即，一种在自然数上归纳构建内容的方法。

假设您要测试 n 是否为 0，只需编写 n true (λm. false)（其中 true 和 false 表示布尔值，但它们可以真的是什么）。然后你有

0 true (λm. false) = true
1 true (λm. false) = (λm. false) true = false
2 true (λm. false) = (λm. false) ((λm. false) true) = false
...

意味着您可以将 0 与其他教会数字区分开来。基本上，当你输入一个教会数字 b 和 f 时，你将 0 的图像作为 b 和一个函数 f 从 [= 的图像29=] 到 n+1.

的图像

写succ函数给自然数加一，你想在它的表示前加一s：

succ n = λz.λs.s (n z s)

n z s 是删除前两个 λ 的同义词。

现在可以用同样的方式表示列表。列表可以是空列表（[] 或 nil）或附加到其他列表 (tail) 的某些元素 (head)：head :: tail 或cons head tail。我们使用相同的技巧： nil 是 λn.λc.n，cons x nil 是 λn.λc.c x n，cons y (cons x nil) 是 λn.λc.c y (c x n)，等等

类似地，您可以将基本情况和函数提供给列表以执行 fold。

cons x (cons y nil) b f = f x (f y b)
(cons x1 (cons x2 (... (cons xn nil) ...))) b f = f x1 (f x2 (... (f xn b) ...)))

要获得长度，您必须注意 nil 的长度是 0 而 cons x l 的长度是 succ (length l)，而不依赖于 x。所以 length l = l 0 (λ_.λn. succ n).

您应该继续构建这样的原语以最终解决您的问题。

接下来你要编写 firstn 函数，它接受一个整数 n 和一个列表 l 并且 return 是 n 的第一个元素。基本上你有

firstn 0 l = nil
firstn (n+1) nil = nil
firstn (n+1) (cons a l) = cons a (firstn n l)

所以你先对自然数做一个分析，然后就行了。我将把它写成一个接受自然数的函数，return一个接受列表的函数，return一个列表。

firstn = λn. n (λl. nil) (λr.λl. l nil (λa.λl. cons a (r l)))

里面r代表递归调用firstn n，我在定义firstn (n+1).

感觉有点棘手，老实说，知道如何使用具有模式匹配的适当功能语言来编写它会有所帮助。我在 coq 中亲自测试了这些。

也许更容易理解的是首先在列表上编写一个案例分析函数，但为此我们需要构建对。

一对是由两个元素组成的东西，所以从任何一对中你都希望能够观察到这两个元素。

pair a b = λp. p a b

换句话说

pair = λa.λb.λp. p a b

然后您可以轻松地获取一对投影中的第一个和第二个投影。

fst = λp. p (λx.λy.x)
snd = λp. p (λx.λy.y)

可以看到

fst (pair a b) = (pair a b) (λx.λy.x)
               = (λp. p a b) (λx.λy.x)
               = (λx.λy.x) a b
               = a

列表的案例分析就像模式匹配，在ocaml中你会这样写

match l with
| nil -> b
| cons h t -> f h t

意思是如果l是nil我想returnb，如果是cons h t我想returnf h t。

这里没有递归调用，但是，应用l会自动进行递归。特别是，您不能访问 t 而是访问 t 上的递归调用的值。为了避免这种情况，我们将 return 原始列表和我们想要 return 的值都成对使用。

caseL = λl.λb.λf. snd (l (pair nil b) (λx.λr. pair (cons x (fst r) (f x (fst r)))

这样

caseL nil b f = b
caseL (cons x l) b f = f x l

如我们所愿。

现在我们又可以写firstn了。请记住，firstn n 计算列表上的函数删除除 n 第一个元素之外的所有元素。

firstn = λn. n (λl. nil) (λr.λl. caseL l nil (λh.λt. cons h (r t)))

它遵循以下结构

n b (λr. f r)

对应于n上的归纳。对于 0 我们 return 基本情况 b 而对于 n+1 我们得到递归调用的值 r 以产生我们的答案 f r。在我们的例子中，基本情况是函数 firstn 0 ，这意味着函数获取一个列表并将其全部丢弃。递归调用在定义firstn (n+1)时对应的是firstn n，那么我们要对上面的列表进行案例分析，使用firstn n（即r）尾部，如果列表不为空。

firstn 2 = 2 (λl. nil) (λr.λl. caseL l nil (λh.λt. cons h (r t)))
         = (λr.λl. caseL l nil (λh.λt. cons h (r t))) ((λr.λl. caseL l nil (λh.λt. cons h (r t))) (λl. nil))
         = (λr.λl. caseL l nil (λh.λt. cons h (r t))) (λl. caseL l nil (λh.λt. cons h ((λl. nil) t)))
         = (λr.λl. caseL l nil (λh.λt. cons h (r t))) (λl. caseL l nil (λh.λt. cons h nil))
         = λl. caseL l nil (λh.λt. cons h ((λl. caseL l nil (λh.λt. cons h nil)) t))
         = λl. caseL l nil (λh.λt. cons h (caseL t nil (λh.λt. cons h nil)))

因此，如果您仔细观察，您已经可以看出这是一个只会获取列表的前两个元素的函数。

firstn 2 (cons 1 (cons 2 (cons 3 (cons 4 nil))))
= caseL (cons 1 (cons 2 (cons 3 (cons 4 nil)))) nil (λh.λt. cons h (caseL t nil (λh.λt. cons h nil)))
= (λh.λt. cons h (caseL t nil (λh.λt. cons h nil))) 1 (cons 2 (cons 3 (cons 4 nil)))
= cons 1 (caseL (cons 2 (cons 3 (cons 4 nil))) nil (λh.λt. cons h nil))
= cons 1 ((λh.λt. cons h nil) 2 (cons 3 (cons 4 nil)))
= cons 1 (cons 2 nil)

如何使用 lambda 演算编写一个函数来检查数组的对称性？

How to write a function to check the array for symmetry using lambda calculus?

algorithm

haskell

functional-programming

lambda-calculus