実は、「無名関数で再帰する」っていう目標はすでに達成されてる。（気づいてた？
ただ、このままだとリストの長さを調べるという機能限定になってしまう。
そこで、再帰させたい関数を引数として与えると、再帰関数を戻り値（って言っていいのかな？）として返してくれるような関数を作りましょう、というお話し。
それがYコンビネータなるものらしい。
理論は極めて数学的な内容なので、突っ込まないでね。
興味がある人はWikipediaの「ラムダ計算」のページを参照されたし。
イメージとしては、
gosh> ((Y (lambda (length) (lambda (l) (cond ((null? l) 0) (else (+ 1 (length (cdr l)))))))) '(foo bar baz)) 3 gosh> ((Y (lambda (fact) (lambda (n) (cond ((< n 2) 1) (else (* n (fact (- n 1)))))))) 5) 120
こんな動きをしてくれる関数Yを作ってみようか、ということらしい。
「変化する部分は切り出して差し替え可能にする」ってあたり、すこしOO的な匂いもする...かな？
あ、ちなみに前者はリストの長さ、後者は階乗の計算をしているところね。
さて、予告編はこれくらいに。
多分167ページまでは終わったと言って問題ないと思う。
167ページの上から2つ目のやりとり
- L
どんな風に動くん？
- R
関数がまさに終わろうとした途端に、mk-length自身を引数としてmk-lengthに渡しつつ再帰評価をし続ける感じやな。
ってあるけど、「じゃあ、おまえはいつそれが分ったんや」とRightcolumn氏を小一時間問い詰めたくなる感じだ。
実際に評価してみた形跡がないやんけ、と。
自分はというと、評価の過程をid:yagiey:20080408でやってるYO！
どこまでいっても
(mk-length mk-length)
が出現する様をヤツはこう言ってるんやね。たぶん。
...っと、不満を漏らしてたら、ちゃんとやってましたねこの人たち。
でもなぜか知らんけど、
(mk-length mk-length)
を外側に追い出す形に書き換えてる。つまり、
((lambda (mk-length) (mk-length mk-length)) (lambda (mk-length) ((lambda (length) (lambda (l) (cond ((null? l) 0) (else (+ 1 (length (cdr l))))))) (mk-length mk-length))))
こんな形。書き換えることで何かいいことあるんかいな？...まぁ、いいや。
この形からスタートしてid:yagiey:20080408みたいな感じで書き直していってる。
じゃあ、自分もやってみっか。
こいつは、
(lambda (mk-length) ((lambda (length) (lambda (l) (cond ((null? l) 0) (else (+ 1 (length (cdr l))))))) (mk-length mk-length)))
の部分をfと置くと
((lambda (mk-length) (mk-length mk-length)) f)
という形をしている。また出たな、このパターン。
これは
(f f)
っていう形に書き換えられるから、fを元に戻すと
((lambda (mk-length) ((lambda (length) (lambda (l) (cond ((null? l) 0) (else (+ 1 (length (cdr l))))))) (mk-length mk-length))) (lambda (mk-length) ((lambda (length) (lambda (l) (cond ((null? l) 0) (else (+ 1 (length (cdr l))))))) (mk-length mk-length))))
ってなる。(f f)の前のfに相当する部分の引数mk-lengthは、後ろのfに相当する部分に置き換えられるから、この関数は
((lambda (length) (lambda (l) (cond ((null? l) 0) (else (+ 1 (length (cdr l))))))) ((lambda (mk-length) ; ←これ ((lambda (length) (lambda (l) (cond ((null? l) 0) (else (+ 1 (length (cdr l))))))) (mk-length mk-length))) (lambda (mk-length) ((lambda (length) (lambda (l) (cond ((null? l) 0) (else (+ 1 (length (cdr l))))))) (mk-length mk-length)))))
と同値ですな。同じ要領でさらにコメントの「←これ」の箇所のmk-lengthに引数をわたしてやると
((lambda (length) (lambda (l) (cond ((null? l) 0) (else (+ 1 (length (cdr l))))))) ((lambda (length) (lambda (l) (cond ((null? l) 0) (else (+ 1 (length (cdr l))))))) ((lambda (mk-length) ((lambda (length) (lambda (l) (cond ((null? l) 0) (else (+ 1 (length (cdr l))))))) (mk-length mk-length))) (lambda (mk-length) ((lambda (length) (lambda (l) (cond ((null? l) 0) (else (+ 1 (length (cdr l))))))) (mk-length mk-length))))))
となる。
あー疲れた。
こんな感じで、いつまでたってもmk-lengthの自己適用が続きますなぁ、と。
なんだか以前やったことの繰り返しになってしもうたな。
「schemerはこの種の関数を考えるときには、どんな思考過程を辿るのだろう。」と言ったけど、自分がやったやり方で良かったみたいだ。
少し自信がついた。
もう少しで9章が終わる。次回終われるかなぁ。
