CODEWITHSUNDEEP
streamracket
gefei
gefei

Reputation: 19856

Order of result of stream-cons

I have a generator for Fibonacci numbers:

(require racket/generator)
(define fib (generator ()
            (define (f a b) 
               (yield a)
               (f b (+ a b)))
            (f 1 1)
        ))

And a take function which converts a generator into a stream:

(define (take n gen)
    (define (f a acc) 
    (if (= a n) acc 
        (f (+ a 1) (stream-cons (gen) acc))))
    (f 0 (stream))
)

take-while is pretty similar to take, I thought:

(define (take-while p gen)
    (define (f acc) 
    (let ([x (gen)])
        (if (not (p x)) acc (f (stream-cons x acc)) )))
    (f (stream))
)

But the result is pretty surprising:

(sequence->list (take-while (lambda (x) (< x 100)) fib))
'(89 55 34 21 13 8 5 3 2 1 1)

(sequence->list (take 5 fib))
'(233 377 610 987 1597)

I think the order of the result of take-while is correct, because (stream-cons x y) extends the stream y at the head. But why does take produce the numbers in the other order?

Upvotes: 0

Views: 31

Answers (1)

Shawn
Shawn

Reputation: 52579

Looking at the documentation for stream-cons, we see:

If first-expr is not preceded by #:eager, then first-expr is not evaluated immediately. Instead, stream-first on the result stream forces the evaluation of first-expr (once) to produce the first element of the stream.

Your take function is calling (gen) in the first-expr position, and that's evaluated lazily, so you see the results in increasing order. Your take-while function first calls (gen) and uses its result as the first argument to stream-cons. Since that's just an integer value, there's nothing to compute later, that value is just returned (lazily). Change your take to something like

(define (take n gen)
  (define (f a acc) 
    (if (= a n)
        acc 
        (f (+ a 1) (stream-cons #:eager (gen) acc))))
  (f 0 (stream)))

and you'll see your expected

> (sequence->list (take 5 fib))
'(1597 987 610 377 233)

Note that take and take-while (In the SRFI-1 list library) are normally list functions; redefining them is just going to confuse people.

Upvotes: 1

Related Questions