scheme で実験しながらずっと疑問に思っていたのが、なぜ関数の全体を囲む lazy が必要なのかという事でした。落ち着いて srfi-40 を読むと、map の実装に必要だと書いてありましたが、いまいち納得いかないので、さらに実験してみます。前回までの復習です。
(define (lcar strm) (car (force strm))) ; 遅延用 car (define (lcdr strm) (cdr (force strm))) ; 遅延用 cdr (define (lnull? strm) (null? (force strm))) ; 遅延用 null? (define (ltake strm n) ; 前から n 番目までリストに変換する (if (<= n 0) '() (cons (lcar strm) (ltake (lcdr strm) (- n 1))))) ;; 足し算がおこった時に表示する。 (define (plus a b) (format #t "(+ ~s ~s) " a b) (+ a b)) ;; 全体を delay で囲ったフィボナッチ数列 (define (fib-loop a b) [delay (let ((c (plus a b))) (cons c (fib-loop b c)))]) (define fib [delay (cons 1 (fib-loop 0 1))]) ;(format #t "\n~s => ~s\n\n" '(ltake fib 6) (ltake fib 6))
次に、自作したストリーム用の map 関数です。
;; delay で囲った map 関数 (define (lmap func strm) (delay (if (null? (force strm)) '() (cons (func (lcar strm)) (lmap func (lcdr strm))))))
これを使って、フィボナッチ数列の全ての数を倍にした数列を定義してみます。
;; 倍にする。 (define (double x) (format #t "(double ~s) " x) (* x 2)) (define fib-double (lmap double fib))
gosh> (ltake fib-double 5) (double 1) (+ 0 1) (double 1) (+ 1 1) (double 2) (+ 1 2) (double 3) (+ 2 3) (double 5) (2 2 4 6 10)
余分な delay/force が無くても完璧に動きます。計算量も期待通りです。難点を一つ挙げれば、リストの作成に cons を使っている事です。つまり、ストリーム用のライブラリを書く人は、ストリームという物が必ず (delay (cons ...)) の形をしている事を覚えておかなくては行けません。これでは実装が露出してモジュール性に欠けるというのが srfi-40 のように特別なコンストラクタ stream-cons を使う理由でしょうか? しかしそれでも (stream-delay (stream-cons ...)) という形を強制するなら似たような物だと思うのですが、どうも良くわかりません。
さて、ここでスペースリークが起こるという噂の filter と、filter を使って偶数のフィボナッチ数だけを抜き出してみます。
;; フィルター (define (lfilter p? s) [delay (if (null? (force s)) ; 終端チェック '() (let ((h (car (force s))) ; 現在の値 (t (cdr (force s)))) ; 次の値 (if (p? h) ; 現在の値を調べる (cons h (lfilter p? t)) ; フィルターに引っかかった。 (force (lfilter p? t)))))]) ; フィルターに引っかからなかった。 (define fib-even (lfilter even? fib))
gosh> (ltake fib-even 5) (+ 0 1) (+ 1 1) (+ 1 2) (+ 2 3) (+ 3 5) (+ 5 8) (+ 8 13) (+ 13 21) (+ 21 34) (+ 34 55) (+ 55 89) (+ 89 144) (+ 144 233) (+ 233 377) (2 8 34 144 610)
おお〜！これは興味深い。見てください。lfilter の定義の最後が、もしもフィルターに引っかからなかった場合の処理が (force (lfilter p? t)) のようになって、次の値を force するようになっています。この force が無いと、delay が二重になってしまうからです。言い換えると、フィルターの振る舞いでは、テストに引っかかるまで次々と CDR を force して行く必要があります。
このように、遅延リストでは入力リストよりも出力リストが短くなる場合に、余分に force する必要がある事になります。ここで、delay と違って lazy は force 時に再帰的に実行される事を思い出しました。delay の代わりに lazy を使うと最後の force が不要になるのです。
;; lazy フィルター (define (lfilter-lazy p? s) [lazy (if (null? (force s)) ; 終端チェック '() (let ((h (car (force s))) ; 現在の値 (t (cdr (force s)))) ; 次の値 (if (p? h) ; 現在の値を調べる (cons h (lfilter-lazy p? t)) ; フィルターに引っかかった。 (lfilter-lazy p? t))))]) ; フィルターに引っかからなかった。
というわけで、まとめとしては、srfi-40 において stream-delay と stream-cons の両方を使って二重のサンクを作る理由は、cons の代わりに stream-cons を使いたいから。lazy が必要なのは遅延リストから遅延リストを作る関数で、途中スキップする必要がある場合だと想像がつきました。
