ストリームの作り方

本記事はストリームについて、Schemeを用いて説明しています。 サンプルコードの動作確認を行ったSchemeの処理系、バージョンは以下のとおりです。

Gauche scheme shell, version 0.9.5 [utf-8,pthreads], x86_64-apple-darwin15.6.0

ストリーム

  • データ構造の観点からすると、ただのシーケンス
  • 代入やミュータブルなデータを用いることなく、状態を保持できます
  • 遅延評価を用いることで、無限を扱えます

遅延リスト

  • 遅延リストとは構成時ではなく、選択時に実行されるリスト

上記のみだと説明不足すぎるので、一般的なシーケンスのリストの問題点から説明します。 シーケンスをリストで表現すると、状態がスタックとして積まれ続けるので、計算速度、メモリの使用量的に問題があります。

以下のコードはn番目のフィボナッチ数を求めるものです。完全にリストが作成されるまで値は求まりません。１０番目のフィボナッチ数を求めるには９番目のフィボナッチ数と８番目のフィボナッチ数が求まっていなければならず、９番目のフィボナッチ数を求めるには８番目のフィボナッチ数と７番目のフィボナッチ数が求まってなければならず…

;recursive process

(define (fib-r n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib-r (- n 1))
                 (fib-r (- n 2))))))

n番目のフィボナッチ数を求めるコードをiterative processで書き直したものが以下のようになります。countを格納する場所さえ確保すればよくなりますが、シーケンスとして扱うことはできなくなります。

;iterative process

(define (fib-i n)
  (define (fib-iter a b count)
    (if (= count 0)
        b
        (fib-iter (+ a b) a (- count 1))))
  (fib-iter 1 0 n))

上のrecursive processとiterative processの両方の問題点を解決するためにストリームを用います。ストリームだと遅延評価を用いるため、リストとしてシーケンスを扱うコストを払う必要がなくなります。

まず、以下のようにcons-streamという構成子があるとします。

(cons-stream ＜a＞ ＜b＞)

＜b＞を評価するタイミングをリスト構成時ではなく、＜b＞を選択するタイミングに変更します。 そうすることで、上に書いたrecursive processでフィボナッチ数を計算する際の計算速度、メモリの使用量などの問題が解決されます。 以下のコードでストリームを作成します。(cons-stream ＜a＞ ＜b＞)の＜b＞はstream-cdrでアクセスされてはじめて実行されます。

(define-syntax cons-stream
  (syntax-rules ()
    ((_ a b) (cons a (memo-proc (lambda () b))))))

(define (stream-car stream) (car stream))

(define (stream-cdr stream) (force (cdr stream)))

(define (force delayed-object)
  (delayed-object))

(define (memo-proc proc)
  (let ((already-run? #f) (result #f))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? #t)
                 result)
          result))))

ストリームの動き

では、実際にストリームの動きを見ていきましょう。まずはいくつか関数を簡単に説明をします。

  • (stream-enumerate-interval low high)はlowからhighまでの正の整数のストリームを作成しています
  • (stream-ref s n)はストリームのn番目まで取り出します
  • (stream-map proc . argstreams)はストリームにprocを適用させています
  • (display-line x)はストリームの流れを確認するために標準出力しています
(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream
       low
       (stream-enumerate-interval (+ low 1) high))))

(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

(define (stream-map proc . argstreams)
  (if (stream-null? (car argstreams))
      the-empty-stream
      (cons-stream
       (apply proc (map stream-car argstreams))
       (apply stream-map
              (cons proc (map stream-cdr argstreams))))))

(define (stream-null? stream) (null? stream))

(define the-empty-stream '())

(define (display-line x)
  (display x)
  (newline))

ストリームを構成したタイミングではリストの１番目のみ評価されます。リストの残りは呼ばれるまで、実行されません。

gosh> (define x (stream-map display-line (stream-enumerate-interval 0 10)))
0
x
gosh> (stream-ref x 5)
1
2
3
4
5
#<undef>
gosh> (stream-ref x 7)
6
7
#<undef>

無限のストリーム

ストリームは無限を定義できます。フィボナッチ数列（フィボナッチ数の無限のストリーム）を定義すると、以下のようになります。 再帰で無限ループしているように見えますが、(fibgen b (+ a b))の部分は呼ばれるまでは実行されないので問題ありません。

(define (fibgen a b)
  (cons-stream a (fibgen b (+ a b))))

(define fibs (fibgen 0 1))
gosh> (stream-ref fibs 10)
55

ストリームの加算

ストリーム同士の加算も容易にできます。以下のコードはストリーム同士をを加算する方法でフィボナッチ数列を定義しています。

(define (add-stream s1 s2)
  (stream-map + s1 s2))

(define fibs
  (cons-stream 0
               (cons-stream 1
                            (add-stream (stream-cdr fibs)
                                        fibs))))

gosh> (stream-ref fibs 10)
55
gosh> (stream-ref fibs 100)
354224848179261915075
gosh> (stream-ref fibs 1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
gosh> (stream-ref fibs 10000)
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

参考

  • Structure and Interpretation of Computer Programs