いろんな誤解がだんだん溶けて来たのでまた書きます。
遅延リストを普通の言語で表現する方法には、奇ストリームと偶ストリームの二通りあります。奇ストリームではストリームの CDR にあたる部分(次の値) だけが遅延評価される一方で、偶ストリームでは全体が遅延評価になります。そうすると、例えば、フィボナッチ数の五番目を求めた後のストリームの状態は、? を未実行の部分だとすると、
- 奇ストリーム: (1 (1 (2 (3 (5 . (7 . ?))))))
- 偶ストリーム: (1 (1 (2 (3 (5 . (?))))))
のようになって奇ストリームでは一つ余分に実行されてしまうという事になります。そこで最近の Scheme では偶ストリームが使われています。
と、言う事を前回まで実は深く考えていなくて思い違いをしていました。何となく心の奥底で、
- 奇ストリームの (stream-cons x y) = (cons x (delay y))
- 偶ストリームの (stream-cons x y) = (delay (cons x (delay y)))
のように、偶ストリームというのは単に奇ストリームに余分な delay を付けたものだと思っていたのですが、実際は
- 偶ストリームの (stream-cons x y) = (delay (cons x y))
のように、y の部分(CDR部) を勝手に遅延する事は無いです。もしも私が思い込んでいたように CDR まで勝手に遅延すると次の値を求める時に二重の delay が出来てしまいます。前回は、この二重の delay を防ぐために lazy が使われるのではと思ったのですが、本来の定義では関係ない事が分かりました。実は他の意味で二重にする事でちょっと良い事もあるのですが、それも含めて復習します。
復習
遅延リストに便利な関数を定義します。
(define (lcar pair) (car (force pair))) ; 遅延用 car (define (lcdr pair) (cdr (force pair))) ; 遅延用 cdr (define (ltake pair n) ; 前から n 番目までリストに変換する (if (<= n 0) '() (cons (lcar pair) (ltake (lcdr pair) (- n 1))))) ;; 遅延評価の確認用に、足し算が起こった時に表示する。 (define (plus a b) (format #t "(+ ~s ~s) " a b) (+ a b)) ;; 全体と CDR を lazy で囲ったもの (define (fib-1-loop a b) [lazy (cons b [lazy (fib-1-loop b (plus a b))])]) (define fib-1 (fib-1-loop 0 1))
最後の fib-1 は前回紹介した物と同じですが、遅延評価の部分を [ カギ括弧 ] で囲っています。カギ括弧は丸括弧と同じ意味ですが、遅延している事が分かりやすいように使い分けてみました。
gosh> (ltake fib-1 6) (+ 0 1) (+ 1 1) (+ 1 2) (+ 2 3) (+ 3 5) (1 1 2 3 5 8)
これを使って六番目までのフィボナッチ数列を表示すると、ちゃんと最後の 3 + 5 までで計算が止まってる事が分かります。かしこい!
delay を一度に一つだけ使う
しかしこれでは全体を囲む lazy と次の値を生む CDR の lazy が二重になって、美しくないです。CDR で足し算するのではなく、CAR で足し算すれば CDR を遅延する必要が無いです。
;; 全体を delay で囲ったもの (define (fib-2-loop a b) [delay (let ((c (plus a b))) (cons c (fib-2-loop b c)))]) (define fib-2 [delay (cons 1 (fib-2-loop 0 1))])
gosh> (ltake fib-2 6) (+ 0 1) (+ 1 1) (+ 1 2) (+ 2 3) (+ 3 5) (1 1 2 3 5 8)
すばらしい! しかしその代償として、let を使ったローカル変数と、数列の最初に足りない 1 の追加が必要です。プログラムは複雑に見えますが、delay が一つしか無いので動作は追いやすいと思います。
逆に二重の delay や lazy がある事の利点は、CDR で次の値を求める事でローカル変数を減らせる事かもしれません。
srfi-40 を使う
さて、今までは delay や lazy を使って自力でストリームを作ってきましたが、最初からライブラリにストリーム専用の関数が用意されています。これで労力が削減出来るか微妙ですが、ストリーム用の便利な関数が沢山あるし、型チェックにもなるのでライブラリを使った方が良いと思います。いくつか srfi-40 のライブラリ関数を使った例を書きます。
;; srfi-40 stream-delay だけを使ったもの (define (fib-3-loop a b) [stream-delay (let ((c (plus a b))) (cons c (fib-3-loop b c)))]) (define fib-3 [stream-cons 1 (fib-3-loop 0 1)]) ;; srfi-40 stream-cons だけを使ったもの (define (fib-4-loop a b) [stream-cons b (fib-4-loop b (plus a b))]) (define fib-4 (fib-4-loop 0 1)) ;; srfi-40 stream-delay を外に stream-cons を中に使ったもの (define (fib-5-loop a b) [stream-delay (let ((c (plus a b))) [stream-cons c (fib-5-loop b c)])]) (define fib-5 [stream-cons 1 (fib-5-loop 0 1)]) ;; srfi-40 stream-cons を外に stream-delay を中に使ったもの (define (fib-6-loop a b) [stream-cons b [stream-delay (fib-6-loop b (plus a b))]]) (define fib-6 (fib-6-loop 0 1))
stream-delay と stream-cons の意味は次のようになっています。
- (stream-delay x) = (lazy x)
- (stream-cons x y) = (delay (cons x y))
srfi-40 の文書では、fib-5 の stream-delay を外に stream-cons を中に使ったスタイルしか出てこないので、これを推奨しているのだと思います。私としては fib-6 の stream-cons を外に stream-delay を中に使ったスタイルの方が好きですが、lazy の本来の引き数は promise なので、反則かもしれません。
fib-4 は一見スマートですが、stream-cons は勝手に CDR を遅延する事はしないので一つ余分に計算してしまいます。
gosh> (ltake fib-4 6) (+ 0 1) (+ 1 1) (+ 1 2) (+ 2 3) (+ 3 5) (+ 5 8) (1 1 2 3 5 8)
そんなわけで、なかなかややこしい物です。
