Lazy stream of random(s): When does evaluation happen?

user_876937 0
Viewed 111

The following code, I thought, should define a stream of random numbers between 1 and 10:

(define random-stream (stream-cons (random 1 11) random-stream))

However, what it actually does is define a stream of a specific random number. For example:

> (stream->list (stream-take random-stream 10))
'(5 5 5 5 5 5 5 5 5 5)

I presume this is the random number that (random 1 11) produces when the definition is first parsed. I got around this by making random-stream an argument-less function:

(define (random-stream) (stream-cons (random 1 11) (random-stream)))

This works:

> (stream->list (stream-take (random-stream) 10))
'(6 1 10 9 4 2 2 3 3 10)

So it looks to me that constants are, understandably, evaluated at read time, whereas functions are evaluated at call time. Usually this wouldn't matter, but in the case of a stream -- where you've got a recursive definition -- this makes a difference.

Is this how it works, or is it more subtle than this? Are there other cases one should be aware of regarding this difference?

racket scheme lazy-evaluation random stream
2 Answers

Making random-stream an argument-less function is the correct solution.

(define (random-stream) (stream-cons (random 1 11) (random-stream)))

I will explain why.

When you define a stream normally with (define my-stream (stream-cons ....)), there is only one value for the stream. Any reference to my-stream will produce the same value.

(define my-stream (stream-cons (random 1 11) my-stream))

The my-stream inside the "rest" is literally the same value eq? to the one my-stream.

> (eq? my-stream (stream-rest my-stream))
#true

So because they are the same value, they can be substituted in function calls. If (stream-first my-stream) returns 5, then (stream-first (stream-rest my-stream)) must also return 5. (This is because stream-first is a "pure" function in the sense that it returns the same output for the same inputs.)

> (eq? (stream-first my-stream) (stream-first (stream-rest my-stream)))
#true

This is not the case with the function version because every time the function is called it creates a new stream value.

(define (random-stream) (stream-cons (random 1 11) (random-stream)))

> (eq? (random-stream) (random-stream))
#false
> (eq? (stream-first (random-stream)) (stream-first (random-stream)))
#false

Since the "rest" field also calls (random-stream), the rest is different from the whole.

> (define generated-stream (random-stream))
> (eq? generated-stream (stream-rest generated-stream))
#false
> (eq? (stream-first generated-stream) (stream-first (stream-rest generated-stream)))
#false
user_54325010

I agree with the other answer that the problem with OP code is that random-stream is a stream for which (stream-first random-stream) is some random number, while (stream-rest random-stream) is also the same stream beginning with the same number.

I don't quite agree with "an argument-less function is the correct solution," though.

One alternative solution would be to use stream-map to map random numbers over the natural numbers:

(define random-stream/1-10
  (stream-map (lambda (x) (random 1 11)) (in-naturals)))

It would be even better to create a function that makes a stream of random numbers:

(define (random-stream a b)
  (stream-map (lambda (x) (random a b)) (in-naturals)))

This function can be used to create a stream (note that in-naturals is also a function that creates streams):

random_streams.rkt> (define my-stream (random-stream 1 11))
random_streams.rkt> (stream->list (stream-take my-stream 10))
'(1 1 2 7 5 7 4 2 2 9)

Using this idea of a function that creates streams, the stream-cons method can be rescued:

(define (random-stream-cons a b)
  (stream-cons (random a b) (random-stream-cons a b)))

When stream-first is called on a stream created with random-stream-cons, a random number is returned; when stream-rest is called on the same stream, another stream with a random number as its first element is returned.

The created streams are persistent:

random_streams.rkt> (stream->list (stream-take random-stream/1-10 10))
'(10 9 9 1 2 7 6 2 6 6)
random_streams.rkt> (stream->list (stream-take random-stream/1-10 15))
'(10 9 9 1 2 7 6 2 6 6 10 1 2 8 5)

random_streams.rkt> (define my-stream-1 (random-stream 1 11))
random_streams.rkt> (stream->list (stream-take my-stream-1 10))
'(1 4 1 10 7 9 9 9 2 9)
random_streams.rkt> (stream->list (stream-take my-stream-1 15))
'(1 4 1 10 7 9 9 9 2 9 2 3 9 9 10)

random_streams.rkt> (define my-stream-2 (random-stream-cons 1 11))
random_streams.rkt> (stream->list (stream-take my-stream-2 10))
'(10 4 6 1 4 2 10 5 3 6)
random_streams.rkt> (stream->list (stream-take my-stream-2 15))
'(10 4 6 1 4 2 10 5 3 6 1 5 7 5 5)

This random-stream-cons/1-10 function is essentially the same as the earlier random-stream-cons function (but with no arguments); yet neither of them are streams. Both of them are functions that create streams:

(define (random-stream-cons/1-10) (stream-cons (random 1 11) (random-stream-cons/1-10)))

Each time that one of these stream creation functions is called, a new stream is returned:

random_streams.rkt> (stream->list (stream-take (random-stream-cons/1-10) 10))
'(10 8 3 10 8 8 1 8 4 5)
random_streams.rkt> (stream->list (stream-take (random-stream-cons/1-10) 10))
'(1 8 7 3 8 2 2 10 6 5)

This might be just what is desired; such functions are very useful, for example, in iteration contexts:

random_streams.rkt> (for ([x (stream-take (random-stream 1 11) 5)])
                      (displayln x))
2
8
9
1
3

So, functions that return streams are useful, and the resulting streams can be bound to a symbol if desired. For streams that may be needed multiple times with different values, arguments can be provided in custom stream-creation functions. But for one-off streams, stream-map already does the job of returning a stream which can be bound to a symbol just as OP had originally written.

user_68798260
Related