Stream

From CS 61A Wiki
Jump to: navigation, search

A stream is a lazily evaluated linked list. That is, a stream has first and rest fields, where the first is anything and the rest is a stream or the empty stream. The rest of the list is computed only when requested, and once it is computed, it will be saved and returned the next time we request it. Because of the lazy evaluation, streams allow us to create infinite sequences without running out of memory.

ADT

  • cons-stream – makes a new stream
  • stream-car – returns the first of a given stream.
  • stream-cdr – returns the rest of a given stream.
  • the-empty-stream – an empty stream; for finite streams, it serves as the last element
  • stream-null? – returns whether the argument is the-empty-stream

Examples

A finite stream containing the values 1, 2, 3:

(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))

An infinite stream of 1's:

(define ones (cons-stream 1 ones))

An infinite stream of the natural numbers (1, 2, 3, ...):

(define (make-nats n)
    (cons-stream n (make-nats (+ n 1))))
 
(define nats (make-nats 1))

An infinite stream containing the Fibonacci sequence:

(define fib-stream (cons-stream 1 
                                (cons-stream 1
                                             (stream-add fib-stream (stream-cdr fib-stream)))))

In STk, streams that have an unevaluated rest have a "not forced" promise to evaluate the rest:

STk> nats
(1 . #[promise 23b018 (not forced)])

Once the rest is evaluated, the stream has a "forced" promise to evaluate the rest:

STk> (stream-cdr nats) ; force the promise / evaluate the rest
(2 . #[promise 23c688 (not forced)])
STk> nats
(1 . #[promise 23b018 (forced)])

Useful stream functions

stream-add:

(define (stream-add a b)
    (if (stream-null? a)
        a
        (if (stream-null? b)
            b
            (cons-stream (+ (stream-car a) (stream-car b))
                         (stream-add (stream-cdr a)
                                     (stream-cdr b))))))

ss (show stream): outputs the first 10 elements of a stream

STK>  (ss (add-streams ones twos))
(3 3 3 3 3 3 3 3 3 3 ...)

stream-ref: takes in a stream and an index and outputs the element

STK>  (stream-ref nats 1378)
1378

Writing functions on streams

Streams are recursively defined like linked lists, so stream manipulation will be accomplished through recursion. For example, here is stream-map:

(define (stream-map f stream)
    (if (stream-null? stream)
        the-empty-stream
        (cons-stream (f (stream-car stream)) (stream-map f (stream-cdr stream)))))

Sources

Streams, su14 lecture 25