CODEWITHSUNDEEP
streamschemeracketself-referencesicp
Stefan Dorn
Stefan Dorn

Reputation: 599

How Racket streams work in this case?

I am currently learning Racket (just for fun) and I stumbled upon this example:

(define doubles
   (stream-cons
     1
     (stream-map 
        (lambda (x) 
            (begin
                (display "map applied to: ")
                (display x)
                (newline)
                (* x 2)))
        doubles)))

It produces 1 2 4 8 16 ...

I do not quite understand how it works.

So it creates 1 as a first element; when I call (stream-ref doubles 1) it creates a second element which is obviously 2.

Then I call (stream-ref doubles 2) which should force creating the third element so it calls stream-map for a stream which already has 2 elements – (1 2) – so it should produce (2 4) then and append this result to the stream.

Why is this stream-map always applied to the last created element? How it works?

Thank you for your help!

Upvotes: 1

Views: 673

Answers (1)

Alexis King
Alexis King

Reputation: 43842

This is a standard trick that makes it possible for lazy streams to be defined in terms of their previous element. Consider a stream as an infinite sequence of values:

s = x0, x1, x2, ...

Now, when you map over a stream, you provide a function and produce a new stream with the function applied to each element of the stream:

map(f, s) = f(x0), f(x1), f(x2), ...

But what happens when a stream is defined in terms of a mapping over itself? Well, if we have a stream s = 1, map(f, s), we can expand that definition:

s = 1, map(f, s)
  = 1, f(x0), f(x1), f(x2), ...

Now, when we actually go to evaluate the second element of the stream, f(x0), then x0 is clearly 1, since we defined the first element of the stream to be 1. But when we go to evaluate the third element of the stream, f(x1), we need to know x1. Fortunately, we just evaluated x1, since it is f(x0)! This means we can “unfold” the sequence one element at a time, where each element is defined in terms of the previous one:

f(x) = x * 2

s = 1, map(f, s)
  = 1, f(x0), f(x1), f(x2), ...
  = 1, f(1),  f(x1), f(x2), ...
  = 1, 2,     f(x1), f(x2), ...
  = 1, 2,     f(2),  f(x2), ...
  = 1, 2,     4,     f(x2), ...
  = 1, 2,     4,     f(4),  ...
  = 1, 2,     4,     8,     ...

This knot-tying works because streams are evaluated lazily, so each value is computed on-demand, left-to-right. Therefore, each previous element has been computed by the time the subsequent one is demanded, and the self-reference doesn’t cause any problems.

Upvotes: 1

Related Questions