2008/05/06

オレリスプでYコンビネータ

やっぱりリストの再帰ができないとリスプとはいえない。Yコンビネータが定義できるかやってみよう。Yコンビネータを使うと、関数に名前を付けずに再帰ができる。まあ、なんというか、「ラムダだけでここまでできる」みたいなのがうれしい。

これがYコンビネータ("The Little Schemer"より)。
es20> (define Y 
(lambda (le)
((lambda (f) (f f))
(lambda (f) (le (lambda (x) ((f f) x)))))))
(この「Y」という名前は再帰に使うための名前じゃない。)

たとえばリストの長さを計算する関数なら、こんなふうに実現できる。ちっとも再帰関数には見えないかもだけど、Yコンビネータのなかで「再帰する」ことが抽象化されている感じ。
es24> ((Y (lambda (len)
(lambda (l)
(if (null? l)
0
(+ 1 (len (cdr l)))))))
(quote (beans beans we need jelly beans)))
6.000000
なんかちゃんと動いてる!

にしても、もともと「アトムか、ドットペアか」というだけのルールでS式をパーズしようという企画だったので、いまから「'」記法を導入するのはやっかいだなあ。

あと、この例ではnull?を使っているけど、null?は組み込んではいない。null?とか自分のなかで定義するのがリスプなんだと思う。
es0> (define null? 
(lambda (ls)
(if (eq? (quote ()) ls)
#t #f)))


No comments :