Streams are a sequential data structure containing elements computed only on demand. They are sometimes also called lazy lists.
Streams get constructed with list-like constructors. A stream is either null or is a pair with a stream in its cdr. Since elements of a stream are computed only when accessed, streams can be infinite. Once computed, the value of a stream element is cached in case it is needed again.
When used effectively, the primary benefit of streams is improved modularity. Consider a process that takes a sequence of items, operating on each in turn. If the operation is complex, it may be useful to split it into two or more procedures in which the partially-processed sequence is an intermediate result. If that sequence is stored as a list, the entire intermediate result must reside in memory all at once; however, if the intermediate result is stored as a stream, it can be generated piecemeal, using only as much memory as required by a single item. This leads to a programming style that uses many small operators, each operating on the sequence of items as a whole, similar to a pipeline of unix commands.
In addition to improved modularity, streams permit a clear exposition of backtracking algorithms using the “stream of successes” technique, and they can be used to model generators and co-routines. The implicit memoization of streams makes them useful for building persistent data structures, and the laziness of streams permits some multi-pass algorithms to be executed in a single pass. Savvy programmers use streams to enhance their programs in countless ways.
There is an obvious space/time trade-off between lists and streams; lists take more space, but streams take more time (to see why, look at all the type conversions in the implementation of the stream primitives). Streams are appropriate when the sequence is truly infinite, when the space savings are needed, or when they offer a clearer exposition of the algorithms that operate on the sequence.
(lispkit stream)library provides two mutually-recursive abstract data types: An object of type
streamis a promise that, when forced, is either
stream-nullor is an object of type
stream-pair. An object of the
stream-pairtype contains a
stream-cdr, which must be a stream. The essential feature of streams is the systematic suspensions of the recursive promises between the two data types.
The object stored in the
stream-pairis a promise that is forced the first time the
stream-caris accessed; its value is cached in case it is needed again. The object may have any type, and different stream elements may have different types. If the
stream-caris never accessed, the object stored there is never evaluated. Likewise, the
stream-cdris a promise to return a stream, and is only forced on demand.
The design of the API of library
(lispkit stream)is based on Philip Bewig's SRFI 41. The implementation of the library is LispKit-specific.
Symbol representing the
type-forprocedure of library
(lispkit type)returns this symbol for all stream objects.
stream-nullis a stream that, when forced, is a single object, distinguishable from all other objects, that represents the null stream.
stream-nullis immutable and unique.
#tif obj is a stream; otherwise
stream-null?is a procedure that takes an object obj and returns
#tif the object is the distinguished null stream and
#fotherwise. If object obj is a stream,
stream-null?must force its promise in order to distinguish
stream-pair?is a procedure that takes an object and returns
#tif the object is a
#fotherwise. If object is a stream,
stream-pair?must force its promise in order to distinguish
(stream-cons obj strm)
stream-consis a special form that accepts an object obj and a stream strm and creates a newly-allocated stream containing a stream that, when forced, is a
stream-pairwith the object in its
stream-carand the stream in its
stream-consmust be syntactic, not procedural, because neither object obj nor stream is evaluated when
stream-consis called. Since
strmis not evaluated, when the
stream-pairis created, it is not an error to call
stream-conswith a stream that is not of type stream; however, doing so will cause an error later when the
stream-pairis accessed. Once created, a
(define s (stream-cons 1 (stream-cons 2 (stream-cons 3 stream-null))))
(stream-car s) ⇒ 1
(stream-car (stream-cdr s)) ⇒ 2
stream-caris a procedure that takes a stream strm and returns the object stored in the
stream-carof the stream.
stream-carsignals an error if the object passed to it is not a
stream-carcauses the object stored there to be evaluated if it has not yet been; the object’s value is cached in case it is needed again.
stream-cdris a procedure that takes a stream strm and returns the stream stored in the
stream-cdrof the stream.
stream-cdrsignals an error if the object passed to it is not a
stream-cdrdoes not force the promise containing the stream stored in the
stream-cdrof the stream.
(stream obj ...)
streamis syntax that takes zero or more objects obj and creates a newly-allocated stream containing in its elements the objects, in order. Since
streamis syntactic, the objects are evaluated when they are accessed, not when the stream is created. If no objects are given, as in
(stream), the null stream is returned.
(stream-lambda formals expr0 expr1 ...)
stream-lambdacreates a procedure that returns a stream to evaluate the body of the procedure. The last body expression to be evaluated must yield a stream. As with the regular
lambda, formals may be a single variable name, in which case all the formal arguments are collected into a single list, or it is a list of variable names, which may be
nullif there are no arguments, proper if there are an exact number of arguments, or dotted, if a fixed number of arguments is to be followed by zero or more arguments collected into a list. The body expr0 expr1 ... must contain at least one expression, and may contain internal definitions preceding any expressions to be evaluated.
(define iter (stream-lambda (f x) (stream-cons x (iter f (f x)))))
(define nats (iter (lambda (x) (+ x 1)) 0))
(stream-car (stream-cdr nats)) ⇒ 1
(stream-lambda (s1 s2)
(stream-cons (+ (stream-car s1) (stream-car s2))
(stream-add (stream-cdr s1) (stream-cdr s2)))))
(define evens (stream-add nats nats))
(stream-car evens) ⇒ 0
(stream-car (stream-cdr evens)) ⇒ 2
(stream-car (stream-cdr (stream-cdr evens))) ⇒ 4
(define-stream (name arg ...) expr0 expr1 ...)
define-streamcreates a procedure name that returns a stream, and may appear anywhere a normal define may appear, including as an internal definition, and may have internal definitions of its own, including other
define-streams. The defined procedure takes arguments arg ... in the same way as
define-streamis syntactic sugar on
(stream-let tag ((var val) ...) expr1 expr2 ...)
stream-letcreates a local scope that binds each variable var to the value of its corresponding expression val. It additionally binds tag to a procedure which takes the bound variables as arguments and body as its defining expressions, binding the tag with
stream-lambda. tag is in scope within body, and may be called recursively. When the expanded expression defined by the
stream-letevaluates the expressions expr1 expr2 ... in its body in an environment containing the newly-bound variables, returning the value of the last expression evaluated, which must yield a stream.
stream-letprovides syntactic sugar on
stream-lambda, in the same manner as normal
letprovides syntactic sugar on normal
lambda. However, unlike normal
tagis required, not optional, because unnamed
(display-stream strm n) (display-stream strm n sep) (display-stream strm n sep port)
display-streamdisplays the first n elements of stream strm on port port using string sep as a separator string. If n is not provided, all elements are getting displayed. If sep is not provided,
", "is used as a default. If port is not provided, the current output port is used.
list->streamtakes a list of objects lst and returns a newly-allocated stream containing in its elements the objects in the list. Since the objects are given in a list, they are evaluated when
list->streamis called, before the stream is created. If the list of objects is null, as in
(list->stream '()), the null stream is returned.
port->streamtakes a port port and returns a newly-allocated stream containing in its elements the characters on the port. If the port is not given, it defaults to the current input port. The returned stream has finite length and is terminated by
(stream->list strm n)
stream->listtakes a natural number n and a stream strm and returns a newly-allocated list containing in its elements the first n items in the stream. If the stream has less than n items, all the items in the stream will be included in the returned list. If n is not given, it defaults to infinity, which means that unless the stream is finite,
stream->listwill never return.
(stream-append strm ...)
stream-appendreturns a newly-allocated stream containing in its elements those elements contained in its argument streams strm ..., in order of input. If any of the input streams is infinite, no elements of any of the succeeding input streams will appear in the output stream; thus, if
(stream-append x y)≡
stream-concattakes a stream strms consisting of one or more streams and returns a newly-allocated stream containing all the elements of the input streams. If any of the streams in the input stream is infinite, any remaining streams in the input stream will never appear in the output stream.
(stream-constant obj ...)
stream-constanttakes one or more objects obj ... and returns a newly-allocated stream containing in its elements the objects, repeating the objects in succession forever.
(stream-drop strm n)
stream-dropreturns the suffix of the input stream strm that starts at the next element after the first n elements. The output stream shares structure with the input stream; thus, promises forced in one instance of the stream are also forced in the other instance of the stream. If the input stream has less than n elements,
stream-dropreturns the null stream.
(stream-drop-while pred? strm)
stream-drop-whilereturns the suffix of the input stream that starts at the first element x for which
#f. The output stream shares structure with the input stream.
(stream-filter pred? strm)
stream-filterreturns a newly-allocated stream that contains only those elements x of the input stream for which
(stream-fold proc base strm)
stream-foldapplies a binary procedure proc to base and the first element of stream strm to compute a new base, then applies the procedure proc to the new base (1st argument of proc) and the next element of stream (2nd argument of proc) to compute a succeeding base, and so on, accumulating a value that is finally returned as the value of
stream-foldwhen the end of the stream is reached. strm must be finite, or
stream-foldwill enter an infinite loop.
stream-scan, which is similar to
stream-fold, but useful for infinite streams.
stream-foldis a left-fold; there is no corresponding
right-foldrelies on finite streams that are fully-evaluated, at which time they may as well be converted to a list.
(stream-for-each proc strm ...)
stream-for-eachapplies a procedure proc elementwise to corresponding elements of the input streams strm ... for its side-effects.
stream-for-eachstops as soon as any of its input streams is exhausted.
(stream-from first delta)
stream-fromcreates a newly-allocated stream that contains first as its first element and increments each succeeding element by delta. If delta is not given it defaults to 1. first and delta may be of any numeric type.
stream-fromis frequently useful as a generator in
stream-ofexpressions. See also
stream-rangefor a similar procedure that creates finite streams.
(stream-iterate proc base)
stream-iteratecreates a newly-allocated stream containing base in its first element and applies proc to each element in turn to determine the succeeding element.
stream-lengthtakes an input stream strm and returns the number of elements in the stream. It does not evaluate its elements.
stream-lengthmay only be used on finite streams as it enters an infinite loop with infinite streams.
(stream-map proc strm ...)
stream-mapapplies a procedure proc elementwise to corresponding elements of the input streams strm ..., returning a newly-allocated stream containing elements that are the results of those procedure applications. The output stream has as many elements as the minimum-length input stream, and may be infinite.
(stream-match strm-expr (pattern [fender] expr) ...)
stream-matchprovides the syntax of pattern-matching for streams. The input stream strm-expr is an expression that evaluates to a stream and is matched against a number of clauses. Each clause
(pattern [fender] expr)consists of a pattern that matches a stream of a particular shape, an optional fender that must succeed if the pattern is to match, and an expression that is evaluated if the pattern matches.
There are four types of patterns:
(): Matches the null stream
(pat0 pat1 ...): Matches a finite stream with length exactly equal to the number of pattern elements
(pat0 pat1 ... . patrest): Matches an infinite stream, or a finite stream with length at least as great as the number of pattern elements before the literal dot
pat: Matches an entire stream. Should always appear last in the list of clauses; it’s not an error to appear elsewhere, but subsequent clauses could never match
Each pattern element pati may be either:
- An identifier: Matches any stream element. Additionally, the value of the stream element is bound to the variable named by the identifier, which is in scope in the fender and expression of the corresponding clause. Each identifier in a single pattern must be unique.
- A literal underscore: Matches any stream element, but creates no bindings.
The patterns are tested in order, left-to-right, until a matching pattern is found. If fender is present, it must evaluate as non-
#ffor the match to be successful. Pattern variables are bound in the corresponding fender and expression. Once the matching pattern is found, the corresponding expression is evaluated and returned as the result of the match. An error is signaled if no pattern matches the input stream.
(stream-of expr rest ...)
stream-ofprovides the syntax of stream comprehensions, which generate streams by means of looping expressions. The result is a stream of objects of the type returned by expr. There are four types of clauses:
(var in stream-expr): Loop over the elements of
stream-expr, in order from the start of the stream, binding each element of the stream in turn to
stream-rangeare frequently useful as generators.
(var is expr): Bind
varto the value obtained by evaluating
(pred? expr): Include in the output stream only those elements
(pred? x)is non-
The scope of variables bound in the stream comprehension is the clauses to the right of the binding clause (but not the binding clause itself) plus the result expression. When two or more generators are present, the loops are processed as if they are nested from left to right; i.e. the rightmost generator varies fastest. A consequence of this is that only the first generator may be infinite and all subsequent generators must be finite. If no generators are present, the result of a stream comprehension is a stream containing the result expression; thus,
(stream-of 1)produces a finite stream containing only the element 1.
(stream-range first past)
(stream-range first past delta)
stream-rangecreates a newly-allocated stream that contains first as its first element and increments each succeeding element by step. The stream is finite and ends before past, which is not an element of the stream. If step is not given it defaults to 1 if first is less than past and
-1otherwise. First, past and step may be of any numeric type.
stream-rangeis frequently useful as a generator in
(stream-ref strm n)
stream-refreturns the n-th element of stream, counting from zero. An error is signaled if n is greater than or equal to the length of stream.
stream-reversereturns a newly-allocated stream containing the elements of the input stream strm but in reverse order.
stream-reversemay only be used with finite streams; it enters an infinite loop with infinite streams.
stream-reversedoes not force evaluation of the elements of the stream.
(stream-scan proc base strm)
stream-scanaccumulates the partial folds of an input stream strm into a newly-allocated output stream. The output stream is the base followed by
(stream-fold proc base (stream-take i stream))for each of the first
ielements of stream.
(stream-take strm n)
stream-taketakes a non-negative integer n and a stream and returns a newly-allocated stream containing the first n elements of the input stream. If the input stream has less than n elements, so does the output stream.
(stream-take-while pred? strm)
stream-take-whiletakes a predicate pred? and a stream strm and returns a newly-allocated stream containing those elements
xthat form the maximal prefix of the input stream for which
(pred? x)is non-
(stream-unfold mapper pred? generator base)
stream-unfoldis the fundamental recursive stream constructor. It constructs a stream by repeatedly applying generator to successive values of base, in the manner of
stream-iterate, then applying mapper to each of the values so generated, appending each of the mapped values to the output stream as long as
(pred? base)is non-
(stream-unfolds proc seed)
stream-unfoldsreturns n newly-allocated streams containing those elements produced by successive calls to the generator proc, which takes the current
seedas its argument and returns n+1 values:
(proc seed) → seed result0 ... resultn-1
where the returned seed is the input seed to the next call to the generator and resulti indicates how to produce the next element of the i-th result stream:
(value): value is the next car of the result stream
#f: no value produced by this iteration of the generator
procfor the result stream
(): the end of the result stream
It may require multiple calls of
procto produce the next element of any particular result stream.
(stream-zip strm ...)
stream-ziptakes one or more input streams strm ... and returns a newly-allocated stream in which each element is a list (not a stream) of the corresponding elements of the input streams. The output stream is as long as the shortest input stream, if any of the input streams is finite, or is infinite if all the input streams are infinite.