自然数字的教堂数字编码是否不必要地复杂？

Question

我正在阅读的《计算机程序的结构和解释》 本书通过定义零和增量函数来呈现教会数字 通用标签

这对我来说似乎很复杂，花了我很长时间才能弄清楚并得出一个（λf.λx. f x）和两个（λf.λx. f (f x)）。

以这种方式对数字进行编码会更简单吗，而零是空的lambda？ 通用标签

现在，派生一个（λ. λ）和两个（λ. λ. λ），以此类推。

这似乎是一种用lambda表示数字的更为直接和直观的方式。这种方法是否存在问题，因此是教会数字按其方式工作的充分理由吗？这种方法已经得到证明吗？

Answer 1

您的编码（零：λx.x，一：λx.λx.x，二：λx.λx.λx.x等）使定义增量和减量变得容易，但是除此之外，开发用于编码的组合器变得非常棘手。例如，您将如何定义isZero？

考虑教堂编码的一种直观方法是，通过反复执行基因标记代码时间的动作来表示数字基因标记代码。这使得仅使用数字编码的迭代就可以轻松开发诸如n的组合器。无需花哨的组合器即可递归。

在Church编码中，每个数字都有相同的接口：它带有两个参数。在进行编码时，每个数字都由它所采用的参数数来定义，这使得统一操作确实很棘手。

编码数字的另一种方法是将数字视为n= 0 | |。S n，并对联合使用香草编码。

Answer 2

提议的数字语法在lambda演算中无效，而教堂数字确实在lambda演算中有效。因此，这就是教堂数字使用数字的可能原因-数字编码必须遵守lambda微积分的定义，它还允许在lambda演算中定义的进一步操作（例如，增量）对编码的数字进行操作。