streamschemesicplazy-sequences

# SICP 3.52 delayed cdr

``````(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

• ``````#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.