2023-12-05 19:12
著名的逻辑学家Alonzo Church设计了lambda演算, 想要将其作为数学的基础. 若是要达成此目的, 那么须编码常见的数学对象, 比如说自然数. Church思考了一个方案, 现在被称为Church数码. 它的想法是, 还是请读者直接阅读代码吧.
你能理解吗? 如果理解的话, 就请读者编写two, three, four.
好了, 如果读者学过一点数学的话, 大概会接触自然数系的构造. 我们知道, 后继是最基本的运算. 后继在Church数码中也是很容易的.
有了后继, 加法其实就很简单了, 因为m+n不过就是对于m施行n次后继, 而Church编码下的n本来就是进行重复应用的.
真正有趣的一个话题是, 前继该怎么编写呢? 这可能是一个比较难的问题, 因为Church想了很久也没想出来. 在他快要放弃的时候, 他的学生, 同样也是著名的逻辑学家, 即Kleene, 终于想出来了. 这个故事和笑气有那么点关系, 也和拔智齿有那么点关系. 但是, 讲了也没什么意思.
这是Kleene的答案, 注意这里的cons是单参数的 (Currying的版本).
你能想出来一个更好的答案吗? (更简单, "效率"更高, ...)