streamschemesicplazy-sequences

SICP 3.52 delayed cdr


Exercise 3.52,

(define sum 0)

(define (accum x)
  (set! sum (+ x sum))
  sum)

;1: (define seq (stream-map accum (stream-enumerate-interval 1 20)))
;2: (define y (stream-filter even? seq))
;3: (define z (stream-filter (lambda (x) (= (remainder x 5) 0))
;                           seq))

;4: (stream-ref y 7)
;5: (display-stream z)

Step 1: ;1: ==> (cons-stream 1 (stream-map proc (stream-cdr s)) (Assume stream-cdr is evaluated only when we force the cdr of this stream)

sum is now 1

Step 2: 1 is not even, hence (also memoized so not added again), it calls (stream-filter pred (stream-cdr stream)). This leads to evaluation of cdr hence materializing 2 which is even, hence it should call: (cons-stream 2 (stream-cdr stream)).

According to this answer should be 1+2 = 3 , but it is 6

Can someone help with why the cdr's car is materialized before the current cdr is called?


Solution

  • Using Daniel P. Friedman's memoizing tail

    #lang r5rs
    
    (define-syntax cons-stream
      (syntax-rules () 
        ((_ h t) (cons h (lambda () t)))))
    
    (define (stream-cdr s)
      (if (and (not (pair? (cdr s)))
               (not (null? (cdr s))))
          (set-cdr! s ((cdr s))))
      (cdr s))
    

    we observe:

    > sum
    0
    > (define seq (stream-map accum (stream-enumerate-interval 1 20)))
    > sum
    1
    > seq
    (mcons 1 #<procedure:friedmans-tail.rkt:21:26>)
    > (define y (stream-filter even? seq))
    > sum
    6
    > seq
    (mcons
     1
     (mcons
      3
      (mcons 6 #<procedure:friedmans-tail.rkt:21:26>)))
    > y
    (mcons 6 #<procedure:friedmans-tail.rkt:21:26>)
    > 
    

    stream-filter? needs to get to the first element of the stream it is constructing in order to construct it. A stream has its head element already forced, calculated, so it must be already present.

    In the list of accumulated sums of the enumerated interval from 1 to 20, the first even number is 6:

    1      = 1
    1+2    = 3
    1+2+3  = 6
    ...
    

    Run in Racket.

    To see more, name the enumerating sequence as well: (define nums (stream-enumerate-interval 1 20)), (define seq (stream-map accum nums)), and inspect nums as well as seq etc., while trying the expressions one by one.