成功函数的定义

Definition of success function

在教堂数字中,如果我们有:

# (define zero (lambda (f) (lambda (x) x)))
zero = lambda f: lambda x: x

那么后继函数可以定义为:

# (define succ (lambda (n) (lambda (f) (lambda (x) (f ((n f) x))))))
succ = lambda n: lambda f: lambda x: f(n(f)(x))

也许这是一个愚蠢的问题,但如果后继者本质上是在前面的等式中再添加一个包装器 f(...),为什么不能将其定义为 f(n)?这是为了定义的一致性,还是为什么不能使用更短的形式?

(注意:这里使用 python 定义和方案,因为它让我测试起来更简单。)

数字 n 定义为函数 f 对某些参数 x.

n 应用

因此,

0 = λf.λx.x
1 = λf.λx.f x
2 = λf.λx.f (f x)
3 = λf.λx.f (f (f (x))
...

请注意,1 与 λf.λx.f 0 不同,因此 succ 0 也不相同。 (其他数字也是如此。)

你的定义,λn.λf.λx.(f n) 会给出

succ 0 = (λn.λf.λx.(f n)) (λg.λy.y)
       = λf.λx.f (λg.λy.y)

这与 1 不同,但是

 (λn.λf.λx.f (n f x)) (λg.λy.y)
= λf.λx.f ((λg.λy.y) f x)
= λf.λx.f ((λy.y) x)
= λf.λx.f x
= 1