Haskell でのコード.あまりにも有名.
main = print $ take 10 fib
where
fib = 0 : 1 : (zipWith (+) fib $ tail fib)
[0,1,1,2,3,5,8,13,21,34]
real 0m0.003s
user 0m0.000s
sys 0m0.000s
十分シンプル. fib!!0
, fib!!1
までは、cons
によって与えられ、例えば fib!!2
は
fib!!2 = head (zipWith (+) .. ..)
= (head fib) + (head $ tail fib)
= 0 + (head (1 : ..))
= 0 + 1
何も問題ない.
Scheme での実験.Gauche 0.9.3 には、プリミティブ型としてのlconsが あり、cdrにのみ、遅延が入るconsであり、しかもこれは、一度評価したら その値をメモしておく.
上の Haskell でのコードをほとんどそのまま翻訳したもの.
(use gauche.lazy)
(define fib
($ lcons* 0 1 $ lmap + fib $ cdr fib))
(define (main _)
($ display $ take fib 10))
*** ERROR: Attempt to recursively force a lazy pair.
Stack Trace:
_______________________________________
0 ((with-module gauche.internal %zip-nary-args) args)
At line 73 of "/usr/local/share/gauche-0.9/0.9.3.3/lib/gauche/lazy.scm"
1 (take fib 10)
[unknown location]
などと実行時エラーを吐く. (info 'lcons)
を見てると、そのまんま、このコードはバグを含んでいて、「不幸にも」 Gaucheはこれを計算できないのだと書いてある.
即ち、(lcons a b)
はb
のみを遅延するが、それ自体を評価するときに aとbを計算してしまう.
(lcons* a b c) ;; (lcons a (lcons b c))
ならば、まず a
, b
を計算する. cdr部の評価の時に、b
, c
c を計算する.bは先の計算結果がメモされている.
gosh> (define a (lcons* (display "car\n") (display "cadr\n") (display "caddr\n")))
car
cadr
a
gosh> (car a)
#<undef>
gosh> (cadr a)
caddr
#<undef>
だから問題なのは、fib!!1
に相当する (cadr fib)
の計算には、これはそもそも (car (cdr fib))
であり、 (cdr fib)
の計算とは、(cadr fib)
及び (cddr fib)
である.だから fib!!1
の評価に fib!!2
の計算が伴い、そしてそれには (cdr fib)
が必要である.よって無限の再帰が行われる.
頭3つを用意して、またmapの計算を直してやれば、 (\(Fib_n\)を計算するのに, \(Fib_{n-2}\)と \(Fib_{n-1}\) を用いることになるから) よくて.
(use gauche.lazy)
(define fib
($ lcons* 0 1 1 $ lmap (cut $ + <> $ * <> 2) fib $ cdr fib))
(define (main _)
($ display $ take fib 10))
(0 1 1 2 3 5 8 13 21 34)
real 0m0.052s
user 0m0.040s
sys 0m0.008s
綺麗じゃない