ふつうの言語で Lazy list について考える(3)。

おお、id:SaitoAtsushi さんのおかげで何か思いついたので書きます。まず余分な cdr 計算しないようにした遅延評価版フィボナッチ数列です。

(define lfib
  (delay
    (let loop ((a 0) (b 1))
      (cons a (delay (loop b (+ a b)))))))

すばらしい。。。

さて、何らかの理由で、名前付き let が使いたくないと考えます(理由は聞かないでください)。これをこのまま再帰的な関数に翻訳するとこんな感じになるかもしれません。

(define (lfib-delay a b)
  (delay
    (cons b (delay (lfib-delay b (+ a b))))))

しかしこれは動きません！何故かというと、

gosh> (lcar (lfib-delay 0 1))
1
gosh> (lcar (lcdr (lfib-delay 0 1)))
*** ERROR: pair required, but got #<promise 0x5eaeb0>

二番目の数字を取る所で、delay が二重になってしまうからです。これを避けるには一回 force してから delay すれば良いです。そうすると中に来るのが普通の値の時でも promise の時でも、一重だけの promise が出来ます。

(define (lfib-delay-force a b)
  (delay (force 
	  (cons b (delay (force (lfib-delay-force b (+ a b))))))))

gosh> (ltake (lfib-delay-force 0 1) 10)
(1 1 2 3 5 8 13 21 34 55)

。。。これはややこしい！

さて、SRFI-45 の主張によれば、(delay (force ... があるとちゃんと末尾再帰にならないらしいです(理由は聞かないでください)。という事で、(delay (force ... の代わりに lazy を使います。

(define (lfib-lazy a b)
  (lazy
   (cons b (lazy (lfib2 b (+ a b))))))

gosh> (ltake (lfib-lazy 0 1) 10)
(1 1 2 3 5 8 13 21 34 55)

という事で、

というのが　lazy を使う理由ではないでしょうか。どちらの理由もいまいち納得出来てないので、もう少しゆっくり考えてみます。あと、もしかして lazy があれば delay は不要な気もします。

言語ゲーム