Lazy K方式のYコンビネータは分かりやすいなー

Lazy Kで再帰をしようとしたら以下のようなイディオムを使うんだけど

;; fact
((lambda (x) (x x))
 (lambda (self)
   (lambda (n)
     (if (zero? n)
         1
         (* n ((self self) (- n 1)))))))

このイディオム部分をくくりだすとそれがYになる

(lazy-def '(Y f)
 '((lambda (x) (x x))
   (lambda (self)
     (f (self self)) )))

とても分かりやすい

本来のYコンビネータ

(lambda (g) ((lambda (x) (g (x x)))
             (lambda (x) (g (x x)))))

はLazy K方式の((lambda (x) (x x)) ...) の部分を展開(β変換っていうのかな)した形だなーと気づく

先行評価でもOKなバージョン

; 本来のYコンビネータ
(define Y0 (lambda (g) ((lambda (x) (g (x x)))
                        (lambda (x) (g (x x))))))

; http://blog.livedoor.jp/dankogai/archives/51524324.html など
(define Y1 (lambda (f) ((lambda (g) (lambda (m) ((f (g g)) m)))
                        (lambda (g) (lambda (m) ((f (g g)) m))))))

; http://www.loveruby.net/ja/misc/ycombinator.html
(define Y2 (lambda (f) ((lambda (proc) (f (lambda (arg) ((proc proc) arg))))
                        (lambda (proc) (f (lambda (arg) ((proc proc) arg)))))))

; http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-list/35058
(define Y3 (lambda (g) ((lambda (f) (g (f f)))
                        (lambda (f) (g (lambda (y) ((f f) y)))))))

探してみるといくつかのパターンがあったけど、どれも本来のYコンビネータでは先行評価だと無限再帰になるのでlambdaでラッピングしただけだなーと気づく。

本来のYコンビネータから入らずに先行評価でもOK版Yコンビネータを作っている記事は昔読んだことがあるけどそのときの僕には難しかった

追記 (2010-11-27T22:13:35+09:00)

せっかくだからLazy K方式の先行評価でもOK版を作った

(define Y4 (lambda (f) ((lambda (x) (x x))
                        (lambda (self) (f (lambda (y) ((self self) y)))))))