又是 lambda (WIP)

时隔良久，又忙里偷闲捡起来这东西。

看了这个博客，感觉是很好的补充，又把没理解的东西捡起来试图理解一下。（也是在翻了这作者的博文之后，让我起了好好记录 blog 的念头。

解方程

对于阶乘函数 fact

fact :: Int -> Int
fact n = case n of 
  1 -> 1
  n -> n * fact (n-1)

有一个问题是如何只用 lambda 演算来实现 fact。具体一点来说，需要在 fact 内部不能调用 fact 自身。

一定程度上来说，这个要求是很直观的，因为在函数内部调用 fact 时，fact 自身还没定义完，怎么能够调用它呢？

在上面提到的博文当中，该文作者视函数定义为一个方程（可能也确实是），fact n 后的等号 =，就是数学意义上的等号，等号两侧完全等价。

如果能够利用这个方程，直接解出 fact 的定义，那么也就得到了 fact 的定义，绕过了先有鸡还是先有蛋的问题。

不动点

中学数学里其实很直接少见到递归的概念，偶尔出现也只是出于数列题目，浮光掠影。

然而哪怕只是很少出现，也有人已经把不动点的概念引入到各种高中教辅书里，配上标题：『不动点法求通项公式』，配图往往有两种，一种是一个螺旋状，另一种是折线。（折线的大概长这样）：

       ▲
       │
       │
       │
       │
       │                                                 xx
       │                                                xx               lll
       │                                              xx         lllllllll
       │                                           xxx     llllll
       │                                        xxx lllllll
       │                                     llllllll
       │                               lll▲─►l
       │                         lllll┌───┘x
       │                     lllll    ▲xxx
       │                 lll┌────────►┘x
       │             lllll  ▲      xxx
       │         lllll      │    xx
       │     lllll          │  xx
       lllllll▲─────────────►xx
lllllll│      │            xx
l      │      │         xxx
       │      │       xxx
       │      │     xxx
       │      │    xx         y=x
       │      │  xx
       │      │xx
       │     x│x
       │    xx│
       │  xx  │
───────┘xx────┴───────────────────────────────────────────────────────────────►
      xx
    xx │
   x   │
 xx    │

基本意思就是不动点随着数列趋于极限，将逐步收敛到一个“稳定”的定值。或者干脆就等于这个值，同时因为这个点很“稳定”，于是它不再往外跑，从而得到了一个解。

那时候的理解很粗糙，没能真正弄懂极限与无穷。但是从利用这个工具解题的过程中还是获得了一点认知：谁掌握了不动点，谁就掌握了整个复杂过程的解。

方程例子

上面提到的 blog 里，作者引用的是函数定义上的不动点，即若 f(x)=x，则 x 是 f 的一个不动点。但我觉得数列的例子可能更像一个算法，于是多写了几笔。

言归正传。先从阶乘的例子来看 $Y$ 组合子怎么用。$Y$ 组合子有这样的性质：

Y f = f Y f

也就是说 $Y$ 组合子是这样一个高阶函数：对于任意函数 $f$，$(Yf)$ 都是 $f$ 的一个不动点

f (Y f) = (Y f) ; 函数作用是右结合的

定义对于阶乘函数 fact，定义一个 mk-fact:

(define (mk-fact fact')
  (lambda (n)
    (cond
      ((= n 1) 1)
      (else (* n (fact' (sub1 n)))))))

我擦，看起来好麻烦，我换个随意点的写法：

mk-fact fact' =
  if n = 1  => 1
  else      => n * (fact' (n-1)) ; 意思到了就行

然后直接将 mk-fact 给 $Y$ 组合子：

Y mk-fact = mk-fact (Y mk-fact)

接着传递 n 的时候，神奇的事情发生了:

(Y mk-fact) n 

->
(mk-fact (Y mk-fact)) n

->
if n = 1  => 1
else      => n * ((Y mk-fact) (n-1))

如果记 fact = Y mk-fact，则：

fact n =
  if n = 1  => 1
  else      => n * (fact (n-1))

就此得到了阶乘函数 fact 家人们

Y-combinator

$$\lambda f.(\lambda x.fxx)(\lambda x.fxx)$$

这就是 $Y$ 组合子

随便带入一个 $f$：

$$\begin{array}{rlr}& \lambda f.(\lambda x.fxx)(\lambda x.fxx)f& \\ \to & (\lambda x.fxx)(\lambda x.fxx)& \text{which is exactly }(Yf)\\ \to & f(\lambda x.fxx)(\lambda x.fxx)& (fYf)\\ \to & ff(\lambda x.fxx)(\lambda x.fxx)& (ffYf)\\ \to & ...& \end{array}$$

在 apply 一个具体 f 之后，$Y$ 组合子变成了类似 $\Omega$ 组合子 $(\lambda x.xx)(\lambda x.xx)$ 的东西

此式永远能继续规约，不能规约到一个 normal form，因而说它是发散的（diverge)

如果 $Y$ 作用于自身，直接代入即有 $(\lambda f.Yf)Y=(\lambda f.fYf)Y=YY=YYY$

回过头来

我们总结一下寻找 fact 的过程：

首先，先把 fact 写出来

fact = lambda n.
  if n = 1 => 1
  else => n * (fact (n-1))

抽象一下，就是写一个函数体里有 fact 递归调用的函数

fact = ... fact ...     (1)

然后我们假设 fact 是某个函数 g 的不动点，即 g fact = fact

于是 fact = g fact (2)

于是 g fact = ... fact ... (3)，将 (2) 代回 (1) 即得

现在又已知 Y 组合子能求出任意函数的不动点，Y g = g Y g (4)

于是设 Y g = h，则 g h = h (5)，带入 (4) 即得

于是 g h = ... h ... (6)，将 h 作为 fact 代入 (3) 即得

于是 h = ... h ... 将 (5) 代回 (6)

于是解出了阶乘函数（递归函数）h

简直是魔术