匿名函数的递归

一个简单的递归求列表长度：

(define length
  (λ (l)
    (if (null? l)
        0
        (+ 1 (length (cdr l))))))

如果不允许使用define，如何实现？

先实现一个最简单版本，当列表为空时成立。

(λ (l)
  (if (null? l)
      0
      (+ 1 (...... (cdr l)))))

先忽略......处，显然，当l为空的时候，能得到正确返回0。就叫它lenght0吧。

依托已有的这个函数，来实现当list为1的时候，也能正确返回的函数：

(λ (l)
  (if (null? l)
      0
      (+ 1 (length0 (cdr l)))))

可以看出

和空列表版本几乎一致，唯一的区别是......和length0
由于不让使用define，所以无法直接使用lenght0，需要代换

最终length1如下：

(λ (l)
  (if (null? l)
      0
      (+ 1 ((λ (l)
              (if (null? l)
                  0
                  (+ 1 (...... (cdr l)))))
            (cdr l)))))

再进一步，得到length2，如下：

(λ (l)
  (if (null? l)
      0
      (+ 1 ((λ (l)
              (if (null? l)
                  0
                  (+ 1 ((λ (l)
                          (if (null? l)
                              0
                              (+ 1 (...... (cdr l)))))
                        (cdr l)))))
            (cdr l)))))

如果一直这样写下去，就会得到一个三角形的函数，尝试抽取一部分逻辑，现在已经知道：如果有lengthN函数，那lenghtN+1就是如下

(λ (l)
  (if (null? l)
      0
      (+ 1 (lengthN (cdr l)))))

由于没有define，所以只能将lengthN作为一个参数传入:

(λ (lengthN)
  (λ (l)
    (if (null? l)
        0
        (+ 1 (lengthN (cdr l))))))

重写length0和length1

;length0
((λ (lengthN)
   (λ (l)
     (if (null? l)
         0
         (+ 1 (lengthN (cdr l))))))
 ......)

;length1
((λ (lengthN)
   (λ (l)
     (if (null? l)
         0
         (+ 1 (lengthN (cdr l))))))
 ((λ (lengthN)
    (λ (l)
      (if (null? l)
          0
          (+ 1 (lengthN (cdr l))))))
  ......))

现在可以看出嵌套不再是一个突出的三角形了，但是还有进一步改善的空间。

总结一下上面的三个lambda，用数学函数可以表达成这样

\[\displaylines{ length_0=f(......)\\ length_1=f(length_0) \to length_1 = f(f(......))\\ length_2=f(length_1) \to length_2=f(f(f(......))) } \]

显然，我们可以把$f$给抽出来，它的实际作用是使用lengthN，构造lengthN+1，那就先叫他mk-length吧。

((λ (mk-length)
   (mk-length lengthN))
 (λ (lengthN)
   (λ (l)
     (if (null? l)
         0
         (+ 1 (lengthN (cdr l)))))))

再次代换出length0和length1

;length0
((λ (mk-length)
   (mk-length ......))
 (λ (lengthN)
   (λ (l)
     (if (null? l)
         0
         (+ 1 (lengthN (cdr l)))))))

;length1
((λ (mk-length)
   (mk-length
    (mk-length ......)))
 (λ (lengthN)
   (λ (l)
     (if (null? l)
         0
         (+ 1 (lengthN (cdr l)))))))

现在重新来看一直被忽略的......，会发现:

......不应该被调用
当lengthN支持的N足够大时，......也不会被调用

目前的代码是无法运行的，因为不存在......这个identifier，但只要使用任意合法identifier代替......都能使length0正常运行。

由于在length0的上下文里除了新的常量或者atom，就只有mk-length可以用，那就用mk-length吧。

;length0
((λ (mk-length)
   (mk-length mk-length))
 (λ (lengthN)
   (λ (l)
     (if (null? l)
         0
         (+ 1 (lengthN (cdr l)))))))
;it works

用mk-length代替......还有一个额外的惊喜，为函数lengthN带来了更多的表现形式，因为现在参数lengthN实际上就是mk-length，再次观察一下length0

;重新整理
((λ (mk-length) ;f1
   (mk-length mk-length))
 (λ (mk-length) ;f2
   (λ (l)
     (if (null? l)
         0
         (+ 1 (mk-length (cdr l)))))))

会发现

\[\displaylines{f_1(mk) = mk(mk)\\ f_2(mk)(l) = \begin{cases} 0, & \text{if $l=0$} \\ 1+mk(l-1) \end{cases}\\ \Downarrow\\ f_1(f_2)(l)=\underline{f_2(f_2)(l)}=\begin{cases} 0, & \text{if $l=0$} \\ 1+\underline{f_2(l-1)} \end{cases}\\} \]

看画线处，就能知道，距离递归只有一步，只需要将$f_2$做🤏修改，就能达到递归的效果

\[\displaylines{ f_1(mk) = mk(mk)\\ f_2(mk)(l) = \begin{cases} 0, & \text{if $l=0$} \\ 1+\underline{mk(mk)}(l-1) \end{cases}\\ \Downarrow\\ f_1(f_2)(l)=\underline{f_2(f_2)(l)}=\begin{cases} 0, & \text{if $l=0$} \\ 1+\underline{f_2(f_2)(l-1)} \end{cases}\\ } \]

所以，最终的递归版本length为

((λ (mk-length)
   (mk-length mk-length))
 (λ (mk-length)
   (λ (l)
     (if (null? l)
         0
         (+ 1 ((mk-length mk-length) (cdr l)))))))