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 |#