Sat Feb 16 2013

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であり、しかもこれは、一度評価したらその値をメモしておく．

(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, cc を計算する．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

無限リスト (遅延リスト) を用いた、フィボナッチ数列の計算