[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Chicken-users] Trying to understand srfi-41 (streams)
From: |
Peter Bex |
Subject: |
Re: [Chicken-users] Trying to understand srfi-41 (streams) |
Date: |
Sat, 28 Jan 2017 23:35:21 +0100 |
User-agent: |
Mutt/1.5.23 (2014-03-12) |
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