SICP 読書ノート#35 - 3.5.1 ストリームは遅延リスト (pp.187-192)
いよいよストリームへ。
生まれて初めてその概念に触れたけど驚きの連続。特にdelayとforceによる実装が何とも直截的で素敵すぎる。やはりSICPはもっと早くに読むべきだった…
ストリームを使うには
(2015/08/20追記) 実行環境がRacketの場合、ストリームを使うには2つの方法があります。
racket/streamを使う- 自前でストリームを実装する
racket/streamを使う
- 基本は
racket/streamをrequireするだけ。わりと楽 racket/streamにないものはSICPから転用
#lang racket (require (prefix-in strm: racket/stream)) (define-syntax cons-stream (syntax-rules () ((_ a b) (strm:stream-cons a b)))) (define stream-car strm:stream-first) (define stream-cdr strm:stream-rest) (define stream-null? strm:stream-empty?) (define the-empty-stream strm:empty-stream) ;; form ex 3.50 (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 (list->stream sequence) (if (null? sequence) the-empty-stream (cons-stream (car sequence) (list->stream (cdr sequence))))) (provide (all-defined-out))
ただしこれを使うと常にメモ化されたストリームとなってしまうので、練習問題によっては思ったような挙動となってくれないのが辛いところ。
自前でストリームを実装する
SICPのテキストを参考に自前で実装する。streams.scmという名前で以下のようなファイルを作り、
#lang racket (define (memo-proc proc) (let ((already-run? false) (result false)) (define promise (lambda () (if (not already-run?) (begin (set! result (proc)) (set! already-run? true) result) result))) promise)) #| ;; non-memozied stream (define-syntax cons-stream (syntax-rules () ((_ a b) (cons a (lambda () b))))) |# ;; memoized stream (define-syntax cons-stream (syntax-rules () ((_ a b) (cons a (memo-proc (lambda () b)))))) (define (stream-car s) (car s)) (define (stream-cdr s) ((cdr s))) (define (stream-null? s) (null? s)) (define the-empty-stream '()) (define (stream-ref s n) (if (= n 0) (stream-car s) (stream-ref (stream-cdr s) (- n 1)))) (define (stream-filter pred stream) (cond ((stream-null? stream) the-empty-stream) ((pred (stream-car stream)) (cons-stream (stream-car stream) (stream-filter pred (stream-cdr stream)))) (else (stream-filter pred (stream-cdr stream))))) (define (stream-enumerate-interval low high) (if (> low high) the-empty-stream (cons-stream low (stream-enumerate-interval (+ low 1) high)))) (define (stream-for-each proc s) (if (stream-null? s) 'done (begin (proc (stream-car s)) (stream-for-each proc (stream-cdr s))))) (define (display-stream s) (stream-for-each (lambda (x) (display (format "~a " x))) s) (newline)) ;; from ex 3.50 (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 (list->stream sequence) (if (null? sequence) the-empty-stream (cons-stream (car sequence) (list->stream (cdr sequence))))) (define (stream->list s) (if (stream-null? s) the-empty-stream (cons (stream-car s) (stream->list (stream-cdr s))))) (define (stream-append s1 s2) (if (stream-null? s1) s2 (cons-stream (stream-car s1) (stream-append (stream-cdr s1) s2)))) (define (interleave s1 s2) (if (stream-null? s1) s2 (cons-stream (stream-car s1) (interleave s2 (stream-cdr s1))))) (provide (all-defined-out))
(require "stream.scm")でロードする。
また、メモ化されないストリームとする場合は、以下のコードの方を有効にすればよいです。
;; non-memozied stream (define-syntax cons-stream (syntax-rules () ((_ a b) (cons a (lambda () b)))))
以降は自前のストリームを使って読み進めていきます。
ソースコードはGitHubにアップしているので、良かったら参考にしてみてください。
- https://github.com/uents/sicp/blob/master/ch3/streams.scm
- https://github.com/uents/sicp/blob/master/ch3/racket-streams.scm
ストリーム入門
テキスト通りenumerate-intervalのストリーム版を写経。
(define (stream-enumerate-interval low high) (if (> low high) the-empty-stream (cons-stream low (stream-enumerate-interval (+ low 1) high))))
テスト。ちゃんと動いてる。
racket@> (define s (stream-enumerate-interval 10000 1000000)) racket@> (stream-car s) 10000 racket@> (stream-car (stream-cdr s)) 10001 ;; prime? を使うためにロード racket@> (require math/number-theory) racket@> (define primes (stream-filter prime? s)) racket@> (stream-car primes) 10007 racket@> (stream-car (stream-cdr primes)) 10009
リスト操作で本当に遅延評価されているのか、速度を測ってみる。ストリームなし版のenumerate-intervalは2章で出てきた通り。
(define (enumerate-interval low high) (if (> low high) nil (cons low (enumerate-interval (+ low 1) high))))
テスト。
racket@> (time (list-ref (enumerate-interval 10000 10000000) 10000)) cpu time: 9206 real time: 10190 gc time: 6286 20000 racket@> (time (stream-ref (stream-enumerate-interval 10000 10000000) 10000)) cpu time: 6 real time: 8 gc time: 0 20000
改めて書くまでもないけど、ストリームなし版はenumerate-intervalは先に先頭から終端までのリストを展開してからでないとlist-refを評価できないため時間がかかる。ストリーム版はstream-enumerate-intervalが即座に(cons-stream 10000 (delay (stream-enumerate-interval 10001 10000000)))という対を返し、stream-refが(force (delay ...))で評価して次の要素へ進むというのの繰り返しになるので、参照したい要素まで分の計算しか走らない。よって速度に大きな差が生じる。
練習問題
理解したつもりになったところで練習問題へ。
問題 3.50
以下のstream-mapを完成させよ。穴埋めなのでかなり助かる。
(define (stream-map proc . argstreams) (if (<??> (car argstreams)) the-empty-stream (<??> (apply proc (map <??> argstreams)) (apply stream-map (cons proc (map <??> argstreams))))))
まず2章に戻ってmapの実装を写経する。
(define (mono-map proc items) (if (null? items) nil (cons (proc (car items)) (mono-map proc (cdr items)))))
2章では脚注でちょろっと登場しただけだったが、これの複数リストが扱える版を実装する。
(define (high-map proc . argitems) (if (null? (car argitems)) nil (cons (apply proc (mono-map car argitems)) (apply high-map (cons proc (mono-map cdr argitems))))))
テスト。ちゃんと動いている。
racket@> (mono-map (lambda (n) (+ 1 n)) (list 1 2 3)) '(2 3 4) racket@> (high-map (lambda (n) (+ 1 n)) (list 1 2 3)) '(2 3 4) racket@> (high-map + (list 1 2 3) (list 4 5 6)) '(5 7 9)
これまでの内容だとstream-mapはこのhigh-mapの中をstream手続きに置き換えればよいだけなので、次のようになるはず。
(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))))))
さらに検証用にlist->streamおよびstream->listを実装。
(define (list->stream sequence) (if (null? sequence) nil (cons-stream (car sequence) (list->stream (cdr sequence))))) (define (stream->list s) (if (stream-null? s) nil (cons (stream-car s) (stream->list (stream-cdr s)))))
道具はそろったのでテスト。
racket@> (stream->list (stream-map + (list->stream (list 1 2 3)) (list->stream (list 4 5 6)))) => '(5 7 9)
おお！できてる！
問題 3.51
(define (display-line x) (display x) (newline)) (define (show x) (display-line x) x) (define x (stream-map show (stream-enumerate-interval 0 10)))
とした時に(stream-ref x 5)および(stream-ref x 7)の結果はどうなるか？
メモ化している場合は以下の通り。
racket@> (stream-ref x 5) 1 2 3 4 5 5 racket@> (stream-ref x 7) 6 7 7
続けて(stream->list x)を実行してみると、１度評価された結果はメモされているので1〜7はプリントされない。
racket@> (stream->list x) 8 9 10 '(0 1 2 3 4 5 6 7 8 9 10)
メモ化しない場合は、１度評価されたもので都度評価されるので結果が変わる。
問題 3.52
(define sum 0) (define (accum x) (set! sum (+ x sum)) sum) (define seq (stream-map accum (stream-enumerate-interval 1 20))) (define y (stream-filter even? seq)) (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq))
において、
(stream-ref y 7) (display-stream z)
の実行結果はどうなるか？
まずseqは(stream-enumerate-interval 1 20)の並びに対して、その最初からその項までの和を項とする並びになる。つまり、(stream-enumerate-interval 1 20)を\( \lbrace i_{n} \rbrace = \lbrace 1, 2, 3, ..., 20 \rbrace \) と定義した場合、seqの各項は、
- \( s_{0} = i_{0} \)
- \( s_{1} = i_{1} + i_{0} \)
- \( s_{2} = i_{2} + i_{1} + i_{0} \)
- ...
- \( s_{k} = i_{k} + \sum_{j = 0}^{k - 1} i_{j} \)
となるため \( \lbrace s_{n} \rbrace = \lbrace 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, \dots, 210 \rbrace \) のような並びになる。
よって、(stream-ref y 7) の結果は \( \lbrace s_{n} \rbrace \) の7番目の偶数となるので136、(display-stream z)は \( \lbrace s_{n} \rbrace \) の5の倍数を順次プリントするので10 15 45 55 105 120 190 210が表示されるはず。
テスト。
racket@> (stream-ref y 7) 136 racket@> (display-stream z) 10 15 45 55 105 120 190 210
合ってる。
メモ化をしないストリームではseqを走査する度にsumに値が蓄積されてしまうので、以下のように結果がおかしくなってしまう。
racket@> (stream-ref y 7) 162 racket@> (display-stream z) 15 180 230 305
次は「§3.5.2 無限ストリーム」から。
