Nils M Holm, 2006
A stream is a construct that delivers a potentially infinite series of values. For instance the stream s delivers multiples of 7:
(s) => 7 (s) => 14 (s) => 21 ...
The procedure s that implements above stream obviously has to have some state, because it maps the same argument (none) to different values.
Nevertheless streams can be implemented in a purely functional programming language using higher order functions.
This text describes an implementation of purely functional streams in Scheme.
Each stream may be divided into two parts:
The list may be considered a poor man's version of the stream. It has a current value (its head) and a series of successive values (its rest):
(define lst (list 7 14 21 28 35)) (car lst) => 7 (cdr lst) => (14 21 28 35)
While the head of the list may contain any kind of data, its rest is always a list. The same recursive definition can be applied to the stream.
A stream consists of:
Another advantage of the stream over the list is that a stream does not actually have to store all successive values. An infinite stream, like the one producing multiples of 7, could not do this anyway.
So streams have to have the ability to generate new values during their live times.
Here is a first sketch:
(define (stream1 init rest)
(lambda ()
(cons init
(stream1 (rest init) rest))))
This higher-order function returns a procedure of zero arguments which in turn returns a simple stream:
(define mult7 ((stream1 7 (lambda (x) (+ 7 x))))) mult7 => (7 . #<procedure ()>)
The value of mult7 is a pair whose head contains the current value of the stream and whose tail contains a procedure delivering the rest of the stream:
((cdr mult7)) => (14 . #<procedure ()>)
This procedure demonstrates how to extract some values from the stream:
(define (extract n s)
(cond ((zero? n) '())
(else (cons (car s)
(extract (- n 1)
((cdr s)))))))
(extract 10 mult7) => (7 14 21 28 35 42 49 56 63 70)
The simple construct generated by stream1 possesses all properties of a stream:
It is also purely functional, because it creates a new procedure each time a value is returned. The procedure returning the first of the successive values has no state, but it creates a procedure that returns the second successive value, and so on:
((stream1 7 (lambda (x) (+ 7 x)))) => (7 . p1)
(p1) => (14 . p2)
(p2) => (21 . p3)
...
Although the stream1 procedure works fine in the previous example, it has some shortcomings, the most obvious one being that it cannot handle finite streams:
(define lst ((stream1 '(a b c d) cdr))) (extract 3 lst) => ((a b c d) (b c d) (c d)) (extract 4 lst) => bottom
After requesting the fourth value of lst,
extract tells the stream to generate its fifth
value, which fails when the rest function of
stream1 attempts to take the cdr of
(). At this point the stream fails rather
ungracefully by evaluating to an undefined value.
Another defect of stream1 is that it returns tails of the sequence of successors in the above example rather than the individual values of that sequence.
Finally, the stream1 procedure should return a stream immediately, and not a procedure that returns a stream when applied to no arguments.
Here is a version that remedies these issues:
(define (stream2 init first rest lim final)
(letrec
((new-stream
(lambda (v)
(lambda ()
(cond ((lim v) final)
(else (cons (first v)
(new-stream (rest v)))))))))
((new-stream init))))
First is a function that extracts the current value of the stream, lim checks whether the end of the stream has been reached and final is the value to be returned when the stream runs out of values.
This version of stream2 can handle finite sequences as expected:
(extract 4 (stream2 '(a b c d) car cdr null? #f)) => (a b c d)
Extract does not make use of the lim and final arguments, which handle the end of the sequence internally. As soon as lim detects the end of a sequence, the next application of the rest procedure evaluates to final:
(stream2 '() car cdr null? #f) => #f
Using this feature, a complete stream can be turned into a list using the following code:
(define (stream->list s)
(cond (s (cons (car s)
(stream->list ((cdr s)))))
(else '())))
(stream->list (stream2 '(1 2 3 4 5) car cdr null? #f))
=> (1 2 3 4 5)
Of course, stream->list should not be applied to infinite streams.
Here is a version of the mult7 stream using stream2:
(stream2 7 (lambda (x) x)
(lambda (x) (+ 7 x))
(lambda (x) #f)
#f)))
Looks quite ugly, doesn't it? Let us add some utility functions:
(define (id x) x) (define (none x) #f) (define eos #f)
Using these, the applications of stream2 looks much friendlier:
(stream2 7 id (lambda (x) (+ 7 x)) none eos)
Now let us extract all members of this stream that can be divided by two without a rest. First some more utility functions:
(define eos? not) ; end of stream? (define value car) ; extract current value of s (define (next s) ((cdr s))) ; generate next value of s
And here comes the filter:
(define (find p s)
(cond ((eos? s) eos)
((p (value s)) s)
(else (find p (next s)))))
(define (stream-filter p s)
(let ((nxt (next s)))
(if (eos? nxt) eos (find p nxt))))
(stream-filter even?
(stream2 7 id (lambda (x) (+ 7 x)) none eos))
=> (14 . #<procedure ()>)
Having to apply stream-filter for each filter to be added to the stream is, of course, cumbersome. Furthermore, stream-filter cannot be passed to extract or, for that matter, to any function expecting a stream.
So why not move the filter into the stream? Indeed, why not:
(define (stream init first filter rest lim final)
(letrec
((new-stream
(lambda (v)
(lambda ()
(letrec
((find
(lambda (x)
(cond ((lim x) x)
((filter (first x)) x)
(else (find (rest x)))))))
(let ((nxt (find v)))
(cond ((lim nxt) final)
(else (cons (first nxt)
(new-stream (rest nxt)))))))))))
((new-stream init))))
This is the final version of stream. It adds the filter argument which implements stream-filter internally. The all function is used to implement a default filter that passes through all values:
(define (all x) #t)
The creation of the mult7 stream looks like this now:
(stream 7 id all (lambda (x) (+ 7 x)) none eos)
and the stream traversing a list looks like this:
(stream '(a b c d) car all cdr null? eos)
Using the internal filter, you can easily create a variant of mult7 that produces only even multiples of 7:
(stream 7 id even? (lambda (x) (+ 7 x)) none eos)
What is even more interesting, though, is that you can add additional filters to existing streams by creating higher order streams:
(define m7 (stream 7 id all (lambda (x) (+ 7 x)) none eos)) (define m7e (stream m7 value even? next eos? eos)) (extract 10 m7e) => (14 28 42 56 70 84 98 112 126 140)
Standard procedures like append, map, or
filter work on lists. Using the filtering streams
described in this text, they can be adapted to streams easily.
Because streams are potentially infinite, they cannot be filtered or mapped by applying a predicate to all of their values.
As shown in the previous section, a stream is filtered by adding a higher order stream that implements the desired filter:
(define (filter-stream p s) (stream s value p next eos? eos))
The resulting stream gets its values from the original stream, but passes through only the values that satisfy the predicate p:
(define lst (stream '(a 1 b 2 c 3) car all cdr null? eos)) (extract 3 (filter-stream number? lst)) => (1 2 3)
Mapping a function over a stream works in a similar way. The higher-order stream that is added uses its first argument to apply a given function to each value of the stream:
(define (map-stream f s) (stream s (lambda (s) (f (value s))) all next eos? eos)) (define m7+1 (map-stream (lambda (x) (+ 1 x)) mult7)) (extract 10 m7+1) => (8 15 22 29 36 43 50 57 64 71)
List->stream is another useful utility function that turns a list into a finite stream:
(define (list->stream v) (stream v car all cdr null? eos))
Streams are appended by adding a higher-order stream whose final element is another stream:
(define (append-streams s1 s2)
(stream s1 value all next eos? s2))
(stream->list (append-streams (list->stream '(a b c))
(list->stream '(d e f))))
=> (a b c d e f)
The streams introduced in this text have all properties of lists plus they can be used to represent infinite sequences. They are space-efficient, because they can generate new values on demand. They are purely functional, because they do not carry any state.
Adapting typical list functions, like list-ref,
member, etc to streams is straight-forward.
Streams can also be used to provide an abstract and functional interface to mass data storage. For example, a stream can deliver the lines or the characters of an input file.
The streams implementation discussed in this text provides an elegant and purely functional interface to sequences that are typically represented by using state.
Download the code from this text [scm, 2KB]
Copyright (C) 2006 Nils M Holm < nmh @ t3x . org >