在lambda表達式中如何使用遞歸?
或者說,如何能把一個匿名函數定義成遞歸函數?
自問自答,不明覺厲: Fixed-point combinator
.
=======================================
2014_02_03 更新
看了兩篇Y Combinator的文章, 大抵知道了Y Combinator是怎麼推出來的. 答案就更新一下, 算作一個學習筆記吧..上面 胡鞍鋼 已經說到, 對函數, F(f) = lambda(n)((n == 0) ? 1 : n * f(n-1)), 階乘函數其實是F的不動點,即F(fact)=fact.
而Y是這樣一個函數, 輸入一個函數, 返回它的不動點函數.
它的定義是Y(F)=F(Y(F))大家可以用這個定義下,如果支持lazy evaluation的話, Y(F)就是階乘函數的定義了.不過,
Y(F)=F(Y(F))這個定義, 仍然是匿名定義.
接下來使用scheme來說明如何匿名遞歸的定義Y仍然以階乘函數定義為例,下面用fact表示定義階乘函數的輔助函數, 用fac表示最終定義的階乘函數
首先, 我們會希望這樣做, 假定我們已經定義了階乘函數self, 我們用self來定義階乘函數self, 顯然我們可以直接調用self, 不過這裡我們將self函數作為fact的一個參數傳入, 如此定義:(define (fact self n)
(if (= 0 n)
1
(* n (self (- n 1))))
然後如此計算階乘: (fact fact n)
不過這樣顯然是錯誤的, 因為fact要求兩個參數, 而self只要求一個參數.於是我們修改代碼如下:(define (fact self n)
(if (= n 0)
1
(* n (self self (- n 1))))
如此, 我們已經可以計算階乘了:
不過, 我們似乎更希望用(fact 5)這樣的形式, 於是將上面的代碼再修改為
(define (fact self)
(lambda (n)
(if (= n 0)
1
(* n ((self self) (- n 1))))))
於是...
(define fac
((lambda (self)
(lambda (n)
(if (= n 0)
1
(* n ((self self) (- n 1))))))
(lambda (self)
(lambda (n)
(if (= n 0)
1
(* n ((self self) (- n 1)))))))
於是, 我們修改fact函數的定義. fact原來的定義是:
(define (fact self)
(lambda (n)
(if (= n 0)
1
(* n ((self self) (- n 1))))))
修改為:
(define fact
(lambda (self)
((lambda (F)
(lambda (n)
(if (= n 0)
1
(* n (F (- n 1))))))
(self self))))
(define fac (fact fact))
這樣是可以正確運算的.
這時我們發現, 最開始提到過的 F(f) = lambda(n)((n == 0) ? 1 : n * f(n-1))已經出現在這個fact的定義中了,(define F*
(lambda (F)
(lambda (n)
(if (= n 0) 1
(* n (F (- n 1)))))))
等價於
F(f) = lambda(n)((n == 0) ? 1 : n * f(n-1))
如此, 再修改fact的定義
(define fact
(lambda (self)
(F* (self self))))
(define fac (fact fact))
我們發現這時用fac去計算(fac 3)時, 會陷入死循環. 這是因為有些沒有必要被求值的存在被求值了, 這裡不細說, 應該是lazy evaluation相關的. 不過沒關係, 剛才說過(f x) == ((lambda (y) (f y) x)
如此, 再修改fact的定義(define fact
(lambda (self)
(F* (lambda (x) ((self self) x)))))
(define fac
((lambda (self)
(F* (lambda (x) ((self self) x))))
(lambda (self)
(F* (lambda (x) ((self self) x))))))
(define F*
(lambda (F)
(lambda (n)
(if (= n 0) 1
(* n (F (- n 1)))))))
(define fac
((lambda (F)
((lambda (self)
(F (lambda (x) ((self self) x))))
(lambda (self)
(F (lambda (x) ((self self) x))))))
F*))
定義Y
(define Y
(lambda (F)
((lambda (self)
(F (lambda (x) ((self self) x))))
(lambda (self)
(F (lambda (x) ((self self) x)))))))
(define fac (Y F*))
於是我們定義出了Y組合子, 可以試著用它匿名遞歸地定義其他函數, 比如斐波那契..
(define (Fib-Maker f)
(lambda (n)
(if (&<= n 1)
1
(+ (f (- n 1))
(f (- n 2))))))
(define fib (Y Fib-Maker))
推導用的參考:
Y Combinatormvanier: The Y Combinator (Slight Return)這就是大名鼎鼎的 Y Combinator 啊，匿名遞歸是可以實現的。
比如要求 n 的階乘，怎麼辦呢?
先看階乘的遞歸定義:
f(n) = (n == 0) ? 1 : n * f(n-1)
這個定義右側也用到了 f, 所以看起來得給 f 起個名字。其實有辦法繞過：
先定義這麼一個 (高階) 函數：
F(f) = lambda(n)((n == 0) ? 1 : n * f(n-1))
也就是說，F 的輸入是一個函數 f，輸出是另一個函數 F(f) = g, 這裡 g 滿足
g(n) = (n == 0) ? 1 : n * f(n-1)
這個和階乘的遞歸定義的差別在於，左邊是 g, 右邊是 f, 這完全可以是兩個不同的函數。但如果 g 恰好等於 f, 那麼 g（也就是 f）就是階乘函數。所以，匿名地定義階乘函數，要點在於解這麼一個方程：
F(g) = g
也就是求 (高階) 函數 F 的一個不動點。這正是 Y Combinator 乾的事情。
Scheme 里的定義：
(define Y
(lambda (F)
((lambda (x) (x x))
(lambda (g)
(F (lambda args (apply (g g) args)))))))
(args 那個部分並不重要，那個只是允許函數取多個變數)
現在大家可以試試，如果在 Scheme 里定義了上述高階函數 F, 那麼現在
&> ((Y F) 5)
120
&> ((Y F) 6)
720
&> ((Y F) 7)
5040
Y 滿足 F (Y F) = Y F, 所以 Y F 是 F 的一個不動點（即 F(g) = g 的解），可以用歸納法證明（或者從上面的解釋看出）這個就是階乘函數
在SICP裡面的一道練習題也有介紹：http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-26.html#%_thm_4.21
更新：今天確實擴展了知識。求 5 的階乘，翻譯成 Lua 代碼：
a = (function(n)
return (function(fact)
return fact(fact, n)
end)(function(ft, k)
return k == 1 and 1 or (k * ft(ft, k-1))
end)
end)(5)
更新：在滿足一些要求的語言中可以採用 fixed-point combinator。謝謝 @胡鞍鋼 指正。
唯一的方式是將這個 lambda 表達式付給一個名字（變數）。任何其它方式都僅僅是讓這個名字更局部化而已。作為自己的參數傳遞進去, 在內部調用即可. 模式如下:
(f, x) =&> x &<= 1 ? 1 : x * f(f, x - 1);
我的第一反應，是 arguments.callee 一定是哪裡不對。
推薦閱讀：