前面已经得到一个非递归版本的“递归”求列表长度的函数了。

((λ (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} } \]