streamracket

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?


Solution

  • 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.