SICP問題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)
- 上の各式が評価し終わった時のsumの値
- stream-ref, display-stream式の評価に応じて印字される値
- メモ化版と非メモ化版を使用した場合の違い
ついて述べる問題。
とりあえず何も考えずに実行。
まずはメモ化版を使用した場合
(define sum 0) (define seq (stream-map accum (stream-enumerate-interval 1 20))) ; seq sum ; 1 (define y (stream-filter even? seq)) ; y sum ; 6 (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq)) ; z sum ; 10 (stream-ref y 7) ; 136 sum ; 136 (display-stream z) ; 10 ; 15 ; 45 ; 55 ; 105 ; 120 ; 190 ; 210done sum ; 210
次は非メモ化版を使用した場合
(define sum 0) (define seq (stream-map accum (stream-enumerate-interval 1 20))) ; seq sum ; 1 (define y (stream-filter even? seq)) ; y sum ; 6 (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq)) ; z sum ; 15 (stream-ref y 7) ; 162 sum ; 162 (display-stream z) ; 15 ; 180 ; 230 ; 305done sum ; 362
何故違いが出るのかシミュレートしてみるとこんな感じ。
メモ化版のシミュレーション
(define seq (stream-map accum (stream-enumerate-interval 1 20))) ; => (stream-enumerate-interval 1 20) => (1) ; => (stream-map accum) => ((+ 0 1)) => (1), sum => 1 (define y (stream-filter even? seq)) ; => (stream-filter even? (1))=> () ; => (stream-enumerate-interval 1 20) => (1 2) ; => (stream-map accum) => (1 (+ 2 1)) => (1 3), sum => 3 ; => (stream-filter even?) => () ; => (stream-map accum) => seq => (1 3 (+ 3 3)) => (1 3 6), sum => 6 ; => (stream-filter even?) => (6) (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq)) ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 3 6)) => () ; => (stream-enumerate-interval 1 20) => (1 2 3 4) ; => (stream-map accum) => seq => (1 3 6 (+ 4 6)) => (1 3 6 10), sum=> 10 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 3 6 10)) => (10) (stream-ref y 7) ; => (stream-filter even?) => (6 10) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5) ; => (stream-map accum) => seq => (1 3 6 10 (+ 5 10)) => (1 3 6 10 15), sum => 15 ; => (stream-filter even?) => (6 10) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6) ; => (stream-map accum) => seq => (1 3 6 10 15 (+ 6 15)) => (1 3 6 10 15 21), sum => 21 ; => (stream-filter even?) => (6 10) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7) ; => (stream-map accum) => seq => (1 3 6 10 15 21 (+ 7 21)) => (1 3 6 10 15 21 28), sum => 28 ; => (stream-filter even?) => (6 10 28) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8) ; => (stream-map accum) => seq => (1 3 6 10 15 21 28 (+ 8 28)) => (1 3 6 10 15 21 36), sum => 36 ; => (stream-filter even?) => (6 10 28 36) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9) ; => (stream-map accum) => seq => (1 3 6 10 15 21 28 36 (+ 9 36)) => (1 3 6 10 15 21 36 45), sum => 45 ; => (stream-filter even?) => (6 10 28 36) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10) ; => (stream-map accum) => seq => (1 3 6 10 15 21 28 36 45 (+ 10 45)) => (1 3 6 10 15 21 36 45 55), sum => 55 ; => (stream-filter even?) => (6 10 28 36) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11) ; => (stream-map accum) => seq => (1 3 6 10 15 21 28 36 45 55 (+ 11 55)) => (1 3 6 10 15 21 36 45 55 66), sum => 66 ; => (stream-filter even?) => (6 10 28 36 66) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12) ; => (stream-map accum) => seq => (1 3 6 10 15 21 28 36 45 55 66 (+ 12 66)) => (1 3 6 10 15 21 36 45 55 66 78), sum => 78 ; => (stream-filter even?) => (6 10 28 36 66 78) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13) ; => (stream-map accum) => seq => (1 3 6 10 15 21 28 36 45 55 66 78 (+ 13 78)) => (1 3 6 10 15 21 36 45 55 66 78 91), sum => 91 ; => (stream-filter even?) => (6 10 28 36 66 78) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13 14) ; => (stream-map accum) => seq => (1 3 6 10 15 21 28 36 45 55 66 78 91 (+ 14 91)) => (1 3 6 10 15 21 36 45 55 66 78 91 105), sum => 105 ; => (stream-filter even?) => (6 10 28 36 66 78) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15) ; => (stream-map accum) => seq => (1 3 6 10 15 21 28 36 45 55 66 78 91 105 (+ 15 105)) => (1 3 6 10 15 21 36 45 55 66 78 91 105 120), sum => 120 ; => (stream-filter even?) => (6 10 28 36 66 78 120) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16) ; => (stream-map accum) => seq => (1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 (+ 16 120)) => (1 3 6 10 15 21 36 45 55 66 78 91 105 120 136), sum => 136 ; => (stream-filter even?) => (6 10 28 36 66 78 120 136) ; (display-stream z) ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 3 6 10 15 21 36 45 55 66 78 91 105 120 136)) => (10 15 45 55 105 120) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17) ; => (stream-map accum) => seq => (1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 (+ 17 136)) => (1 3 6 10 15 21 36 45 55 66 78 91 105 120 136 153), sum => 153 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 3 6 10 15 21 36 45 55 66 78 91 105 120 136 153)) => (10 15 45 55 105 120) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18) ; => (stream-map accum) => seq => (1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 (+ 18 153)) => (1 3 6 10 15 21 36 45 55 66 78 91 105 120 136 153 171), sum => 171 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 3 6 10 15 21 36 45 55 66 78 91 105 120 136 153 171)) => (10 15 45 55 105 120) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19) ; => (stream-map accum) => seq => (1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 (+ 19 171)) => (1 3 6 10 15 21 36 45 55 66 78 91 105 120 136 153 171 190), sum => 190 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 3 6 10 15 21 36 45 55 66 78 91 105 120 136 153 171 190)) => (10 15 45 55 105 120 190) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20) ; => (stream-map accum) => seq => (1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 (+ 20 190)) => (1 3 6 10 15 21 36 45 55 66 78 91 105 120 136 153 171 190 210), sum => 210 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 3 6 10 15 21 36 45 55 66 78 91 105 120 136 153 171 190 210)) => (10 15 45 55 105 120 190 210)
非メモ化版のシミュレーション
(define seq (stream-map accum (stream-enumerate-interval 1 20))) ; => (stream-enumerate-interval 1 20) => (1) ; => (stream-map accum) => ((+ 0 1)) => (1), sum => 1 ; (define y (stream-filter even? seq)) ; => ※ seq は定義時に(1)となっているので更にaccumはされない ; => (stream-filter even? (1))=> () ; => (stream-enumerate-interval 1 20) => (1 2) ; => (stream-map accum) => (1 (+ 2 1)) => (1 3), sum => 3 ; => (stream-filter even?) => () ; => (stream-enumerate-interval 1 20) => (1 2 3) ; => (stream-map accum) => seq => (1 3 (+ 3 3)) => (1 3 6), sum => 6 ; => (stream-filter even?) => (6) (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq)) ; => ※ seq は定義時に(1)となっているので更にaccumはされない ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1)) => () ; => (stream-enumerate-interval 1 20) => (1 2) ; => (stream-map accum) => seq => (1 (+ 2 6)) => (1 8), sum => 8 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8)) => () ; => (stream-enumerate-interval 1 20) => (1 2 3) ; => (stream-map accum) => seq => (1 8 (+ 3 8)) => (1 8 11), sum => 11 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11)) => () ; => (stream-enumerate-interval 1 20) => (1 2 3 4) ; => (stream-map accum) => seq => (1 8 11 (+ 4 11)) => (1 8 11 15), sum => 15 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11 15)) => (15) (stream-ref y 7) ; => (stream-filter even?) => (6) ; => (stream-enumerate-interval 1 20) => (1 2 3 4) ; => (stream-map accum) => seq => (1 3 6 10 (+ 4 15)) => (1 3 6 10 19), sum => 19 ; => (stream-filter even?) => (6) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5) ; => (stream-map accum) => seq => (1 3 6 10 19 (+ 5 19)) => (1 3 6 10 24), sum => 24 ; => (stream-filter even?) => (6 24) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6) ; => (stream-map accum) => seq => (1 3 6 10 19 24 (+ 6 24)) => (1 3 6 10 24 30), sum => 30 ; => (stream-filter even?) => (6 24 30) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7) ; => (stream-map accum) => seq => (1 3 6 10 19 24 30 (+ 7 30)) => (1 3 6 10 24 30 37), sum => 37 ; => (stream-filter even?) => (6 24 30) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8) ; => (stream-map accum) => seq => (1 3 6 10 19 24 30 37 (+ 8 37)) => (1 3 6 10 24 30 45), sum => 45 ; => (stream-filter even?) => (6 24 30) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9) ; => (stream-map accum) => seq => (1 3 6 10 19 24 30 37 45 (+ 9 45)) => (1 3 6 10 24 30 45 54), sum => 54 ; => (stream-filter even?) => (6 24 30 54) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10) ; => (stream-map accum) => seq => (1 3 6 10 19 24 30 37 45 54 (+ 10 54)) => (1 3 6 10 24 30 45 64), sum => 64 ; => (stream-filter even?) => (6 24 30 54 64) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11) ; => (stream-map accum) => seq => (1 3 6 10 19 24 30 37 45 54 64 (+ 11 64)) => (1 3 6 10 24 30 45 64 75), sum => 75 ; => (stream-filter even?) => (6 24 30 54 64) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12) ; => (stream-map accum) => seq => (1 3 6 10 19 24 30 37 45 54 64 75 (+ 12 75)) => (1 3 6 10 24 30 45 64 75 87), sum => 87 ; => (stream-filter even?) => (6 24 30 54 64) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13) ; => (stream-map accum) => seq => (1 3 6 10 19 24 30 37 45 54 64 75 87 (+ 13 87)) => (1 3 6 10 24 30 45 64 75 87 100), sum => 100 ; => (stream-filter even?) => (6 24 30 54 64 100) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13 14) ; => (stream-map accum) => seq => (1 3 6 10 19 24 30 37 45 54 64 75 87 100 (+ 14 100)) => (1 3 6 10 24 30 45 64 75 87 100 114), sum => 114 ; => (stream-filter even?) => (6 24 30 54 64 100 114) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15) ; => (stream-map accum) => seq => (1 3 6 10 19 24 30 37 45 54 64 75 87 100 114 (+ 15 114)) => (1 3 6 10 24 30 45 64 75 87 100 114 129), sum => 129 ; => (stream-filter even?) => (6 24 30 54 64 100 114) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16) ; => (stream-map accum) => seq => (1 3 6 10 19 24 30 37 45 54 64 75 87 100 114 129 (+ 16 129)) => (1 3 6 10 24 30 45 64 75 87 100 114 129 145), sum => 145 ; => (stream-filter even?) => (6 24 30 54 64 100 114) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17) ; => (stream-map accum) => seq => (1 3 6 10 19 24 30 37 45 54 64 75 87 100 114 129 145 (+ 17 145)) => (1 3 6 10 24 30 45 64 75 87 100 114 129 145 162), sum => 162 ; => (stream-filter even?) => (6 24 30 54 64 100 114 162) ; (display-stream z) ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11 15)) => (15) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5) ; => (stream-map accum) => seq => (1 8 11 15 (+ 5 162)) => (1 8 11 15 167), sum => 167 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11 15 167)) => (15) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6) ; => (stream-map accum) => seq => (1 8 11 15 167 (+ 6 167)) => (1 8 11 15 167 173), sum => 174 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11 15 167 173)) => (15) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7) ; => (stream-map accum) => seq => (1 8 11 15 167 173 (+ 7 173)) => (1 8 11 15 167 173 180), sum => 180 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11 15 167 174 182)) => (15 180) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8) ; => (stream-map accum) => seq => (1 8 11 15 167 173 180 (+ 8 180)) => (1 8 11 15 167 173 180 188), sum => 188 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11 15 167 173 180 188)) => (15 180) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9) ; => (stream-map accum) => seq => (1 8 11 15 167 173 180 188 (+ 9 188)) => (1 8 11 15 167 173 180 188 197), sum => 197 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11 15 167 173 180 188 197)) => (15 180) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10) ; => (stream-map accum) => seq => (1 8 11 15 167 173 180 188 197 (+ 10 197)) => (1 8 11 15 167 173 180 188 197 207), sum => 207 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11 15 167 173 180 188 197 207)) => (15 180) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11) ; => (stream-map accum) => seq => (1 8 11 15 167 173 180 188 197 207 (+ 11 207)) => (1 8 11 15 167 173 180 188 197 218), sum => 218 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11 15 167 173 180 188 197 207 218)) => (15 180) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12) ; => (stream-map accum) => seq => (1 8 11 15 167 173 180 188 197 207 218 (+ 12 218)) => (1 8 11 15 167 173 180 188 197 230), sum => 230 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11 15 167 173 180 188 197 207 218 230)) => (15 180 230) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13) ; => (stream-map accum) => seq => (1 8 11 15 167 173 180 188 197 207 218 230 (+ 13 230)) => (1 8 11 15 167 173 180 188 197 230 243), sum => 243 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11 15 167 173 180 188 197 207 218 230 243)) => (15 180 230) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13 14) ; => (stream-map accum) => seq => (1 8 11 15 167 173 180 188 197 207 218 230 243 (+ 14 243)) => (1 8 11 15 167 173 180 188 197 230 243 257), sum => 257 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11 15 167 173 180 188 197 207 218 230 243 257)) => (15 180 230) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15) ; => (stream-map accum) => seq => (1 8 11 15 167 173 180 188 197 207 218 230 243 257 (+ 15 257)) => (1 8 11 15 167 173 180 188 197 230 243 257 272), sum => 272 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11 15 167 173 180 188 197 207 218 230 243 257 272)) => (15 180 230) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16) ; => (stream-map accum) => seq => (1 8 11 15 167 173 180 188 197 207 218 230 243 257 272 (+ 16 272)) => (1 8 11 15 167 173 180 188 197 230 243 257 272 288), sum => 288 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11 15 167 173 180 188 197 207 218 230 243 257 272 288)) => (15 180 230) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17) ; => (stream-map accum) => seq => (1 8 11 15 167 173 180 188 197 207 218 230 243 257 272 288 (+ 17 288)) => (1 8 11 15 167 173 180 188 197 230 243 257 272 288 305), sum => 305 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11 15 167 173 180 188 197 207 218 230 243 257 272 288 305)) => (15 180 230 305) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18) ; => (stream-map accum) => seq => (1 8 11 15 167 173 180 188 197 207 218 230 243 257 272 288 305 (+ 18 305)) => (1 8 11 15 167 173 180 188 197 230 243 257 272 288 305 323), sum => 323 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11 15 167 173 180 188 197 207 218 230 243 257 272 288 305 323)) => (15 180 230 305) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19) ; => (stream-map accum) => seq => (1 8 11 15 167 173 180 188 197 207 218 230 243 257 272 288 305 323 (+ 19 323)) => (1 8 11 15 167 173 180 188 197 230 243 257 272 288 305 323 342), sum => 342 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11 15 167 173 180 188 197 207 218 230 243 257 272 288 305 323 342)) => (15 180 230 305) ; => (stream-enumerate-interval 1 20) => (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20) ; => (stream-map accum) => seq => (1 8 11 15 167 173 180 188 197 207 218 230 243 257 272 288 305 323 342 (+ 20 342)) => (1 8 11 15 167 173 180 188 197 230 243 257 272 288 305 323 342 362), sum => 362 ; => (stream-filter (lambda (x) (= (remainder x 5) 0)) (1 8 11 15 167 173 180 188 197 207 218 230 243 257 272 288 305 323 362)) => (15 180 230 305)
ポイントは定義時にstream-carまで実行されることと、非メモ化版の方ではaccumが再度実行されるため、sumの値が何回も足されること。
