前面已经得到一个非递归版本的“递归”求列表长度的函数了。
((λ (mk-length)
(mk-length mk-length))
(λ (mk-length)
(λ (l)
(if (null? l)
0
(+ 1 ((mk-length mk-length) (cdr l)))))))
再次回想一下,一般所需要的递归形式
\[\displaylines{ f(l)=\begin{cases} 0, & \text{if $l=0$} \\ 1+f(l-1) \end{cases}\\ } \]
所以,需要在上面的函数中,将(mk-length mk-length)
给想办法替换掉。得到一个如下的版本。
((λ (mk-length)
(mk-length mk-length))
(λ (mk-length)
((λ (length)
(λ (l) ;最内层
(if (null? l)
0
(+ 1 (length (cdr l)))))
)
(mk-length mk-length))
))
去执行一下代码就能知道,是无法正常工作的,原因就在于:
- 传进去的
length
是由(mk-length mk-length)
计算而来。 - 之前的计算是放在最内层,一旦
l
满足要求,就不会在内层计算(mk-length mk-length)
- 现在被抽到外面作为值传入,无法得知函数何时该终止,只能无限计算
(mk-length mk-length)
所以,还是需要想办法把这部分操作延迟到内层进行。有个很简单的延迟计算办法,就是将其用lambda裹一层。如下:
((λ (mk-length)
(mk-length mk-length))
(λ (mk-length)
((λ (length) ;length不再提前计算
(λ (l) ;最内层
(if (null? l)
0
(+ 1 (length (cdr l)))))
)
(λ (x) ((mk-length mk-length) x))) ;用lambda包裹一下
))
这个时候,接受length
的lambda已经有通用的感觉了:
接受一个lambda,用接收到的lambda计算下一次递归的条件。
把其提出来
((λ (le)
((λ (mk-length)
(mk-length mk-length))
(λ (mk-length)
(le
(λ (x) ((mk-length mk-length) x)))
))
)
(λ (length)
(λ (l)
(if (null? l)
0
(+ 1 (length (cdr l)))))
)
)
我们甚至可以用define来让其更易懂一点😂
(define length-f
(λ (f)
(λ (l)
(if (null? l)
0
(+ 1 (f (cdr l)))))
))
(define Y
(λ (le)
((λ (f) (f f)) ;f1
(λ (f) ;f2
(le (λ (x) ((f f) x))) ;f3
))
))
(Y length-f)
最终,得到了Y组合子。
简单不严谨证明一下:
\[\displaylines{ \begin{align} f_1(f) &= f(f) & \qquad (1)\\ f_2[le](f) &= le(f_3[f]) & \qquad (2) \\ f_3[f](x) &= f(f)(x) \Rightarrow f_3[f] = f(f) & \qquad (3) \\ \\ Y(le) &= f_1(f_2[le])\\ &\Downarrow(1)\\ &=\underline{f_2[le](f_2[le])}\\ &\Downarrow(2)\\ &=le(f_3[f_2[le]])\\ &\Downarrow(3)\\ &=le(\underline{f_2[le](f_2[le])}) \\ \\ &Y(le) \Rightarrow le(Y(le)) \end{align} } \]