memoizeと不動点

なんか凄いのでとりあえず紹介。
http://www.kmonos.net/wlog/52.php#_0308050827
id:lethevert:20050902:p2でClean版、id:Nabetani:20050901:p2でC++版を書いている方がいます。しかし、このC++版ではboostを使っているのでちょっと反則っぽい気がします。boost::function,boost::bindは関数型的なパラダイムを表現するには便利すぎるので。私はScheme版を書いてみました。

(define (fix g)
  (g(lambda(x)((fix g)x))))

(define (fib-maker f)
  (lambda(x)
    (if (<= x 1)
	1
	(+ (f (- x 1)) (f (- x 2)) ))))

(define fib (fix fib-maker))
(display (map fib '(1 2 3 4 5)))

ほとんどオリジナルのまま書けてしまいますね。論理を変えないように書いただけで実はあまり理解できていなかったりするわけですが。