Re: [Chicken-users] Trying to understand srfi-41 (streams)

[Peter Bex]

On Sat, Jan 28, 2017 at 11:19:01PM +0100, Bahman Movaqar wrote:
> I've been playing around `srfi-41` for an hour now.  It seems to me,
> that regardless of the operations on the stream, the `head` doesn't
> advance.  For example:
> 
>     (define my-stream (list->stream '(0 1 2 3)))
>     (take 2 my-stream)
> 
> At this point I was expecting the stream head to have advanced by 2.
> But this fails:
> 
>     (assert (equal? (stream-car my-stream) 2))
> 
> And of course, upon further investigation, the head hadn't moved an inch
> after `take` or `car`.  What am I missing?

There are two misconceptions here:

The first is that "stream-take" constructs a lazy list of the first four
items.  Because the list is still lazy, it won't have computed anything!

The second is that (stream-take 2 my-stream) has no effect on the value
of my-stream.  It's still a lazy list, even if the first 2 elements would
have been computed already, my-stream still is a reference to the head of
the original list.

You can see how it's evaluated more easily like this:

;; This will print the value when it's evaluated
(define (make-my-stream n)
   (if (= n 0)
       stream-null
       (stream-cons 
         (begin (print "evaluating item " n) n)
         (make-my-stream (sub1 n)))))

(define my-stream (make-my-stream 4))

Now, if after this you do (stream->list my-stream), it will print all
the elements because it will have to compute every element of the lazy
list in order to convert it to a regular list.

If you then do (stream->list my-stream) *again*, it will print the same
end result, but it won't re-evaluate the items because it has already
memoized the computed items.

This is the "magic" of streams: they'll evaluate every element once, and
only once.  But only if strictly necessary!  Thus, stream-take will
produce a new lazy list which will only compute its car when you actually
request it.  It could be defined as:

(define (my-stream-take n stream)
  (if (zero? n)
      stream-null
      (stream-cons
        (stream-car stream)
        (my-stream-take (sub1 n) (stream-cdr stream)))))

As you can see, it immediately calls stream-cons, which means it won't
actually compute anything until you force the car off the result stream.

See also section 3.5 of SICP, available freely online at:
https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5

Hope this helps,
Peter

signature.asc
Description: Digital signature