よーしパパ、関数に名前を付けずに再帰させちゃうぞぉ!(完結編)

  • L

以下の関数におけるmk-lengthを自分自身に適用する部分を関数に置き換えてみ。
(コメントの「←ここ」の箇所)

((lambda (mk-length) (mk-length mk-length))
 (lambda (mk-length)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (+ 1 ((mk-length mk-length) ; ←ここ
		  (cdr l))))))))
  • R

どうやって?

というやりとりから始まるYコンビネータへの道のり。さて、どうなる事やら。
関数に置き換えるのはいいけど、何故そうしろと言うのか理解できない。
まぁ、いいや。言われた通りにするか。

((lambda (mk-length) (mk-length mk-length))
 (lambda (mk-length)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (+ 1 ((lambda (x) ((mk-length mk-length) x))
		  (cdr l))))))))

と、こうなりますな。何がうれしいの?


次に

  • L

新しく作った関数を外へ出してみ。(so以下の意味が取れなかった)

ということなので、書いてみる。

((lambda (mk-length) (mk-length mk-length))
 ...

手が止まった。外へ出すってどこまで出したらえぇの?
「新しく作った関数」いうのは

(lambda (x) ((mk-length mk-length) x))

の部分やって言うのは分かる。
この部分を引数として受け取るようにしろ、って言ってるのも分かる。
だけど、lambdaをどこに書いたらえぇの?
分からんから答えを見た。

((lambda (mk-length) (mk-length mk-length))
 (lambda (mk-length)
   ((lambda (length)
      (lambda (l)
	(cond
	 ((null? l) 0)
	 (else (+ 1 (length (cdr l)))))))
    (lambda (x) ((mk-length mk-length) x)))))

やと。なぜ

(lambda (length)

の位置はそこなのよ?

((lambda (mk-length) (mk-length mk-length))
 (lambda (mk-length)
   (lambda (l)
     ((lambda (length)
	(cond
	 ((null? l) 0)
	 (else (+ 1 (length (cdr l))))))
      (lambda (x) ((mk-length mk-length) x))))))

じゃダメなの?ちゃんと動くよ?
もしくは、なんで

(lambda (mk-length)

の上じゃないの?


分からん!


で、今度は

  • L

コード中の四角で囲った部分を外に出して、名前を付けてみ。(四角で囲ってあるコードは以下の通り)

(lambda (length)
  (lambda (l)
    (cond
     ((null? l) 0)
     (else (+ 1 (length (cdr l)))))))
  • R

おk。こいつはmk-lengthに全く依存してないじゃん!

だと。
ここで分かったことがある。それは

(mk-length mk-length)

を新しい関数で置き換えた理由。
要するに、四角で囲った部分からmk-lengthを追い出すための下準備だったわけね。


んじゃ、続きをやっていく

((lambda (le)
   ((lambda (mk-length) (mk-length mk-length))
    (lambda (mk-length)
      (le (lambda (x) ((mk-length mk-length) x))))))
 (lambda (length)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (+ 1 (length (cdr l))))))))

だと。( ´_ゝ`)フーン で?
さっきと同じ疑問だけど、なぜ

(lambda (le)

の場所がそこなわけ?






Yコンビネータに関してWebで調べたり、先を読んだりしたから

(lambda (length)

(lambda (le)

が何故その位置にあるのか、今となっては分かるような気がする。
少なくとも9章はそんなことが多いような気がする。後になって前やったことの意図が分かる感じ?
前者の場合は

(lambda (length)
  (lambda (l)
    (cond
     ((null? l) 0)
     (else (+ 1 (length (cdr l)))))))

を一まとまりとして扱いたかったから。
後者の場合は、Yコンビネータの引数leに

(lambda (length) ...

再帰させたい関数として与えたかったから。
...じゃねぇかな。たぶん。


Yコンビネータの部分がライブラリコードで、それに与える関数がクライアントコード的な位置づけ?


ということで、以下のような格好をしたYコンビネータが導出できた。

(define Y
  (lambda (le)
    ((lambda (f) (f f))
     (lambda (f) (le (lambda (x) ((f f) x)))))))


length0_0からYを導く過程は理解できた。
というか、導く過程しか理解できてない。
いきなりYの定義を与えられても、きっと意味が分からん。
Yコンビネータが理解できたかというと、否。
釈然としない。


「リストの長さを調べる関数」でやってみたけど他の再帰関数(例えば階乗計算とか)で同じことをしてみたら少しは理解に近づくかなぁ...。
それともλ計算の勉強した方がいいかな。
んーーー。


そんなこんなで、The Little Schemerの9章が終わったよ。
全然理解できてないけど。 orz