自然数字的教堂数字编码是否不必要地复杂?
-
28-10-2019 - |
题
我正在阅读的《计算机程序的结构和解释》 本书通过定义零和增量函数来呈现教会数字 通用标签
这对我来说似乎很复杂,花了我很长时间才能弄清楚并得出一个(λf.λx. f x
)和两个(λf.λx. f (f x)
)。
以这种方式对数字进行编码会更简单吗,而零是空的lambda? 通用标签
现在,派生一个(λ. λ
)和两个(λ. λ. λ
),以此类推。
这似乎是一种用lambda表示数字的更为直接和直观的方式。这种方法是否存在问题,因此是教会数字按其方式工作的充分理由吗?这种方法已经得到证明吗?
解决方案
您的编码(零:λx.x
,一:λx.λx.x
,二:λx.λx.λx.x
等)使定义增量和减量变得容易,但是除此之外,开发用于编码的组合器变得非常棘手。例如,您将如何定义isZero
?
考虑教堂编码的一种直观方法是,通过反复执行基因标记代码时间的动作来表示数字基因标记代码。这使得仅使用数字编码的迭代就可以轻松开发诸如n
的组合器。无需花哨的组合器即可递归。
在Church编码中,每个数字都有相同的接口:它带有两个参数。在进行编码时,每个数字都由它所采用的参数数来定义,这使得统一操作确实很棘手。
编码数字的另一种方法是将数字视为n= 0 | |。S n,并对联合使用香草编码。
其他提示
提议的数字语法在lambda演算中无效,而教堂数字确实在lambda演算中有效。因此,这就是教堂数字使用数字的可能原因-数字编码必须遵守lambda微积分的定义,它还允许在lambda演算中定义的进一步操作(例如,增量)对编码的数字进行操作。
不隶属于 StackOverflow