Scheme手習い(16) Yコンビネータ
ラスボス1来ました
Yコンビネータってのはこれ
正確には適用順Yコンビネータって言うらしいです
(define Y
(lambda (le)
((lambda (f) (f f))
(lambda (f)
(le (lambda (x) ((f f) x)))))))
何がなんだかわかりません
こんなの読んでふむふむとかわかっちゃう人がいるんでしょうか
恐ろしいです
順番に見ていくしかありません
(define ...)
は何ですか。
何でしょうか
では、再帰的定義とは何ですか。
何でしょう
哲学でしょうか
これはあの
length
関数ですか。(define length (lambda (l) (cond ((null? l) 0) (else (add1 (length (cdr l)))))))
そうですね
次の関数は何をするものでしょう。
(lambda (l) (cond ((null? l) 0) (else (add1 (eternity (cdr l))))))
なんでしょうか
length
とそっくりですけど、eternity
ってあの無限ループするやつでしょうか
空リストの長さを決めますが、ほかには何も決めません。
確かにおっしゃるとおりです
「決める」より「求める」と書いたほうが馴染みがある感じ
> ((lambda (l)
(cond
((null? l) 0)
(else (add1 (eternity (cdr l))))))
'())
0
> ((lambda (l)
(cond
((null? l) 0)
(else (add1 (eternity (cdr l))))))
'(1))
(応答なし)
eternity
の次くらいに部分的な関数ですね
この関数は便宜上length0と呼びます
eternity
のところをlength0自身に置き換えてやると
判定できる要素数がひとつ増えて空リストまたは1要素のリストの長さを求める関数になります
(lambda (l)
(cond
((null? l) 0)
(else (add1 ((lambda (l)
(cond
((null? l) 0)
(else (add1 (eternity (cdr l))))))
(cdr l))))))
これはlength1
この調子でlength2、length3とどんどん置き換えてやれば
任意の数までの要素を含むリストの数が数えられるようになります
でも無限の関数は書くことはできません。
そうですね
これらのプログラムにはすべて
length
に似た関数があります。おそらくこの関数を抽象化する必要があるのでしょう。
どんどん置き換えるかわりに関数呼び出しにするってことですね
DRY原則で
length
と似ているけれども(lambda (length) ...)
で始まる関数が必要です。
なにがしたいんでしょうか
このことでしょうか。
((lambda (length) (lambda (l) (cond ((null? l) 0) (else (add1 (length (cdr l))))))) eternity)
ははーん
define
で名前を付けられないからlambda
の引数にして名前を付けるってわけですね
どうやらここがひとつのミソ
これはlength0を生成します。
たしかに、length
をeternity
に置き換えてやればlength0そのものです
length1は以下のようになります
length0のeternity
の部分をlength0に置き換えてやればできあがり
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
eternity))
引数を置き換えてやればlength1になることはすぐ確認できます
length2から先も同様
でもなにかよくなったんでしょうか?
eternity
のあたりでひとひねりしたらいいことありそうな予感はします
近いですが、まだ繰り返しがあります。
そうですね。コピペコーディングはよくないです
length
を引数として取り、length
に似た関数を返す関数に名前をつけましょう。
「length
を引数として取り、length
に似た関数を返す関数」っていうのはこれですね
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
名前をつけるにはlambda
の引数にすればいいんでした
((lambda (mk-length)
...)
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
これで、...
のところでは「length
を引数として取り、length
に似た関数を返す関数」を
mk-length
と書けるようになりました
「length
を引数として取り、length
に似た関数を返す関数」にeternity
を渡したものが
length0でしたので、length0はこうなります
((lambda (mk-length)
(mk-length eternity))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
length0のeternity
のところをlength0自身に置き換えるとlength1になるんでした
((lambda (mk-length)
(mk-length
(mk-length eternity)))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
おお、重複が消えました
D・R・Y! D・R・Y!
これでたくさん書いても平気です
((lambda (mk-length)
(mk-length
(mk-length
(mk-length
(mk-length eternity)))))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
あとは無限に書けばできあがり!
再帰とはどんなものですか。
任意の関数への
mk-length
の適用が無限に連鎖しているようなものです。
任意の関数?
ってeternity
のこと?
実際に無限の連鎖が必要ですか。
もちろん、そんなことはありません。
長さを調べたいリストは有限ですもんね
何回必要かを推測することはできるでしょうか。
長くても100個まで、とか仕様書に書いてあればいいんですけどそうでなければ無理
たぶん100個くらいで充分なんで、とか言ったら品証の人が怒るんじゃないですかね
十分に大きな数を推測しなかったことはいつわかりますか。
最も内側の
mk-length
に渡されたeternity
を実行するときです。
eternity
を呼んじゃったら負けですね
この時点で
eternity
に対してmk-length
をもう一回実行するように書くとどうなりますか。
言ってる意味がわかりません
どんな関数が
mk-length
に渡されるのか誰も気にしないので、
どうせeternity
は呼ばれちゃいけないので、何を渡しても同じ
だからさっき「任意の関数」って言ってたんですね
最初に
mk-length
を渡すこともできますね。
まあいいんじゃないですかね
なんで渡したいのか知りませんけど
そうすれば、
eternity
に対してmk-length
を適用した結果をcdr
に対して
適用することで、連鎖をもう一段先に進めることができます。
ええとどういうことですか
ええとええと
長過ぎるリストを引数にとったとき、これまで(eternity (cdr l))
ってなってた呼び出しが
((mk-length eternity) (cdr l))
になってくれるってことですかね
最初にeternity
を渡すのをやめてmk-length
を渡すってことは、
((lambda (mk-length)
(mk-length eternity))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
のeternity
をmk-length
に変えるってことですね
((lambda (mk-length)
(mk-length mk-length))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
eternity
がどっかいっちゃいました
さっき思ってたことと違いますね
わかりません!
脳内で動かしてみます
空リストを渡せば0が返ります
空でないリストを渡すとlength0は無限ループに入りましたがこれはどうなるでしょう
連鎖がもう一段先に進むでしょうか?
(1)を渡してみます
l
がnull?
ではないので、(length (cdr l))
つまり(mk-length '())
が呼ばれます
ここでmk-length
は(lambda (length) ...)
でlength
には'()
が渡されます
なんかおかしいです
さらに
length
をmk-length
という名前に変更することさえできます。((lambda (mk-length) (mk-length mk-length)) (lambda (mk-length) (lambda (l) (cond ((null? l) 0) (else (add1 (mk-length (cdr l))))))))
どういうリファクタリングでしょうか
間違いじゃないのはわかるんですけど
なぜ、こんなことをしたいのでしょうか。
気になりますね
すべての名前は同等ですが、ある名前はほかのものよりさらに同等なのです。
何を言っているんでしょうか
そうです。名前は一貫性を持って使えば、それでよいのです。
いややっぱ目的が見えてないと
そして
mk-length
はlength
よりさらに同等な名前なのです。
そう言われてもわかりませんが、今や渡されてるのはmk-length
ですからね
そういうことでしょうか
mk-length
がmk-length
に渡される今となっては、この引数をさらなる再帰を
生成するのに使えますか。はい。
mk-length
を1回適用すればlength1が得られます。((lambda (mk-length) (mk-length mk-length)) (lambda (mk-length) (lambda (l) (cond ((null? l) 0) (else (add1 ((mk-length eternity) (cdr l))))))))
mk-length
が(mk-length eternity)
になりました
(mk-length eternity)
はまんまlength0ですので
さっきと違って再帰呼び出しがエラーになりません
全体としてはlength1になります
(((lambda (mk-length) (mk-length mk-length)) (lambda (mk-length) (lambda (l) (cond ((null? l) 0) (else (add1 ((mk-length eternity) (cdr l)))))))) l)
の値はなんですか。ここで
l
は(apples)
です。
ここは練習
(((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 ((mk-length eternity) (cdr l))))))))
'(apples))
スタート
全体を見ると1〜6行目が関数で、7行目が引数
引数はこのままでいいので関数の方を変形します
1〜6行目の中では、1〜2行目が関数で、3〜6行目が引数
(mk-length mk-length)
のmk-length
を3〜6行目のコードで置き換えます
= (((lambda (mk-length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 ((mk-length eternity) (cdr l)))))))
(lambda (mk-length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 ((mk-length eternity) (cdr l))))))))
'(apples))
今度は、1〜4行目の関数に、5〜8行目の関数を引数として与えます
= ((lambda (l)
(cond ((null? l) 0)
(else (add1 (((lambda (mk-length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 ((mk-length eternity) (cdr l)))))))
eternity) (cdr l))))))
'(apples))
1〜7行目の関数に、(apples)
を引数として与えます
内側のl
は内側のlambda
の引数なので置き換えません
= (cond ((null? '(apples)) 0)
(else (add1 (((lambda (mk-length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 ((mk-length eternity) (cdr l)))))))
eternity) (cdr '(apples))))))
(null? '(apples))
ではないので、
= (add1 (((lambda (mk-length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 ((mk-length eternity) (cdr l)))))))
eternity)
'()))
1〜4行目の関数に、eternity
を引数として与えます
あとはもういいかな
= (add1 ((lambda (l)
(cond ((null? l) 0)
(else (add1 ((eternity eternity) (cdr l))))))
'()))
= (add1 (cond ((null? '()) 0)
(else (add1 ((eternity eternity) (cdr '()))))))
= (add1 0)
= 1
できました
複雑な形でどこから手をつければいいか悩みますが、感覚でなんとか
これは2回以上できますか。
はい。
mk-length
を自分自身に渡し続ければ、必要なだけ実行することができます。次の関数はなんと呼ぶのがよいでしょう。
((lambda (mk-length) (mk-length mk-length)) (lambda (mk-length) (lambda (l) (cond ((null? l) 0) (else (add1 ((mk-length mk-length) (cdr l))))))))
もちろん、lengthです。
ああそうですね
理屈上はね
ってこれ動くの!
> (((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 ((mk-length mk-length) (cdr l))))))))
'(1 2 3))
3
てっきりYコンビネータが完成するまで動かないものだと思ってました
動くと思ってみればたしかに動かない理由はないですね
(mk-length mk-length)
がつまりlength
そのものって感じ