通过显示所有 beta 减少来表明术语“cons”有效

Question

我是函数式编程的新手。

所以术语 cons 将一个元素附加到列表的前面。其中

cons ≜ λx:λl:λc:λn: c x (l c n)

我应该如何着手证明 cons 使用示例函数调用的 beta 缩减可以正常工作？例如减少 cons 3 [2,1] 到 [3,2,1]?

有类似lambda演算中算术运算的公式吗？与算术运算（即加法或乘法）相比，我对如何处理这个问题有点困惑。

谢谢。

Answer 1

cons ≜ λx:λl:λc:λn: c x (l c n)表示

cons x l c n =
   c x (l c n)

（以功能/应用/组合符号表示）。所以

cons 3 [2,1] c n = 
 = c 3 ([2,1] c n)

什么是 [2,1] 如果不只是 cons 2 [1] 的快捷符号以便我们继续

 = c 3 (cons 2 [1] c n)
 = c 3 (c    2 ([1] c n))
 = c 3 (c    2 (cons 1 [] c n))
 = c 3 (c    2 (c    1 ([] c n)))

所以没有从 cons 3 [2,1] 减少到 [3,2,1]； [3,2,1]是cons 3 [2,1]。而[2,1]是cons 2 [1]，而[1]是cons 1 [].

列表 cons x xs，当提供 c 和 n 参数时，将变成 c x (xs c n)，依此类推将 xs, 依次；因此任何列表的元素都在 c 的应用程序链中一个接一个地使用。

[] c n应该变成什么？它没有任何东西可以通过 c 应用程序——这些应用程序将应用于列表的元素，而 [] 有 none。所以唯一合理的做法（我相信你已经给出了这个定义）是把 [] c n 变成 n:

cons 3 [2,1] c n = 
 = c 3 (c    2 (c    1 ([] c n)))
 = c 3 (c    2 (c    1       n ))

无论 c 和 n 是 .

就是这样。

Show that term `cons` works by showing all beta reductions