Yコンビネータ
おとうさん、ぼくにもYコンビネータがわかりましたよ! - きしだのはてな
を読んだけどうまく理解できず以下を読みかえしたがよくわからん。
入門Common Lisp―関数型4つの特徴とλ(ラムダ)計算
- 作者: 新納浩幸
- 出版社/メーカー: 毎日コミュニケーションズ
- 発売日: 2006/09
- メディア: 単行本
- 購入: 2人 クリック: 56回
- この商品を含むブログ (46件) を見る
普通に階乗を書くとこう。
(defun fact (n) (if (= n 0) 1 (* n (fact (1- n))))) >fact (fact 5) >120
Yコンビネータで書くとこう。
(defun Y (f n) (funcall (funcall f f) n)) >Y (defun fact0 (f) (lambda (n) (if (= n 0) 1 (* n (Y f (1- n)))))) >fact0 (Y 'fact0 5) >120
fact0はたしかにfact0を呼び出してない。fをfuncall f fに置き換えて内部から呼び出すのではなく外から注入(DIっぽいw)しているということなのかな。