functional-programming - 用于函数式编程的 lambda 演算

Question

在 lambda 演算 (λ x. λ y. λ s. λ z. xs (ysz)) 中用于两个教堂数字的加法，我们如何解释这一点，有没有什么好的资源用于函数式编程的 lambda 演算？非常感谢您的帮助

Answer 1

实际上λ f1。λ f2。λs。λz。(f1 s (f2 sz)) 计算加法，因为它实际上是将 f2 表示的数字 (f2 sz) 替换为 (f1 sz) 内部的“零”。

示例：让我们s s z以扩展形式为 f2 取两个。f1 是一个：s z. 将最后一个替换z为 f2 ，您将得到s s s z3 的扩展形式。

用黑板和挥手会更容易，抱歉。

Answer 2

在 lambda 演算中，您根据数据类型引发的操作对数据类型进行编码。例如，布尔值只是一个选择函数，它接受输入两个值 a 和 b，并返回 a 或 b：

                      true = \a,b.a   false = \a,b.b

自然数有什么用？它的主要计算目的是提供迭代的界限。因此，我们将一个自然数编码为一个运算符，该运算符接受一个函数 f 和一个值 x 的输入，并将 f 在 x 上的应用迭代 n 次：

                        n = \f,x.f(f(....(f x)...))

f 出现 n 次。

现在，如果要从 x 开始对函数 f 进行 n + m 次迭代，则必须开始迭代 n 次，即 (nfx)，然后再从上一个结果开始迭代 m 次，即

                                m f (n f x)

同样，如果要迭代 n*m 次，则需要迭代 m 次迭代 n 次 f 的操作（如在两个嵌套循环中），即

                                 m (n f) x  

之前的数据类型编码更正式地解释为构造函数和相应的消除器（所谓的 Bohm-Berarducci 编码）。