]> git.rkrishnan.org Git - sicp.git/blob - src/sicp/ex3_52.rkt
Solution to 4.44. A bit too verbose. Can be improved by better
[sicp.git] / src / sicp / ex3_52.rkt
1 #lang planet neil/sicp
2
3 (define (stream-car s) (car s))
4 (define (stream-cdr s) (force (cdr s)))
5
6 (define (stream-ref s n)
7   (if (= n 0)
8       (stream-car s)
9       (stream-ref (stream-cdr s)
10                   (- n 1))))
11
12 (define (stream-map proc s)
13   (if (stream-null? s)
14       the-empty-stream
15       (cons-stream (proc (stream-car s))
16                    (stream-map proc (stream-cdr s)))))
17
18 (define (stream-filter pred? s)
19   (cond [(stream-null? s) the-empty-stream]
20         [(pred? (stream-car s))
21          (cons-stream (stream-car s)
22                       (stream-filter pred? (stream-cdr s)))]
23         [else (stream-filter pred? (stream-cdr s))]))
24
25 (define (stream-for-each proc s)
26   (if (stream-null? s)
27       'done
28       (begin
29         (proc (stream-car s))
30         (stream-for-each proc (stream-cdr s)))))
31
32 (define (display-stream s)
33   (stream-for-each display-line s))
34
35 (define (display-line x)
36   (newline)
37   (display x))
38
39 ;; stream-enumerate-interval
40 (define (stream-enumerate-interval low high)
41   (if (> low high)
42       the-empty-stream
43       (cons-stream low
44                    (stream-enumerate-interval (+ low 1)
45                                               high))))
46
47 #|
48
49 (define sum 0)
50 (define (accum x)
51   (set! sum (+ x sum))
52   sum)
53
54 (define seq (stream-map accum (stream-enumerate-interval 1 20)))
55
56 (define y (stream-filter even? seq))
57
58 (define z (stream-filter (lambda (x) (= (remainder x 5) 0))
59                          seq))
60
61 (stream-ref y 7)
62
63 (display-stream z)
64
65 |#
66
67 #|
68
69 What is the value of sum after each of the above expressions is evaluated? 
70
71 ANS:
72
73 > (define seq (stream-map accum (stream-enumerate-interval 1 20)))
74 1
75
76 This is because (stream-enumerate-interval 1 20) builds up a stream
77 which looks as follows:
78
79 s ==
80
81 (cons 1
82       (delay (cons 2
83                    (delay (cons 3
84                                 (delay .......)))..))
85
86 Now, calling stream-map will produce seq which looks like this:
87
88 seq == (cons (accum (car s))  ;; adds (car s) to sum
89              (delay (stream-map accum (stream-cdr s))))
90     == (cons 1
91              (delay (stream-map accum (stream-cdr s))))
92 |#
93
94 #|
95
96 (define y (stream-filter even? seq))
97
98 This will first run (even? (stream-car seq)) which will be false for
99 the first value (i.e. 1). So, it will do:
100
101 (stream-filter even? (stream-cdr seq))
102
103 Calling stream-cdr on the seq will 'force' the delayed computation.
104 So, seq becomes:
105
106 seq == (cons 1
107              (stream-map accum (stream-cdr s)))
108     == (cons 1
109              (cons (accum 2) ;; sum becomes 3
110                    (delay (stream-map accum (stream-cdr s)))))
111
112 Now, stream-filter will be called with seq as:
113
114  (cons 3
115        (delay (stream-map accum (stream-cdr s))))
116
117 Again, stream-filter will run the car of seq with the predicate:
118
119  (even? (car seq))
120
121 which will be false; Now the new computation will be:
122
123  (cons (accum 3) ;; sum becomes 3 + 3 = 6
124        (delay (stream-map accum (stream-cdr s)))))
125
126 When stream-filter runs the predicate, (even? (stream-car seq))
127 it will return true. At this point, sum = 6.
128
129 |#
130
131 #|
132
133 (define z (stream-filter (lambda (x) (= (remainder x 5) 0))
134                          seq))
135
136 At this point, seq is
137
138 (1 (3 (6 (delay (stream-map accum (stream-cdr s)))))
139
140 The forming of the new value of z will run it thru 1, 3 and 6
141 and finds that they are not multiple of 5. Now, seq is
142
143 (cons (accum 4) ;; sum = 6 + 4 = 10
144       (delay (stream-map accum (stream-cdr s))))
145
146 =
147 (cons 10
148       (delay (stream-map accum (stream-cdr s)))))
149
150 Now, stream-filter will run the predicate and will return
151 true and returns a stream-cons. At this point, sum = 10.
152
153 |#
154
155 #|
156
157 (stream-ref y 7)
158
159 This will take out 7 values out of y, which means 7 even values. So,
160 we produce 16 values in the initial stream before we get 7 even values.
161
162 (cons 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 (delay (cons 17 (delay (cons 18 ...))))
163
164 sum should be
165 (+ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16)
166 = 136
167
168 |#
169
170 #|
171
172 (display-stream z)
173
174 If we were to evaluate seq as a whole and also the rest, we would
175 get the following.
176
177 seq is:
178
179 (1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 210)
180
181 y is
182
183 (10 28 36 66 78 120 136 190 210)
184
185 z is
186
187 (10 15 45 55 95 105 120 190 210) 
188
189 sum is 210
190
191 |#