# LispKit Stream

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.

## Benefits of using streams

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.

## Stream abstractions

The `(lispkit stream)` library provides two mutually-recursive abstract data types: An object of type `stream` is a promise that, when forced, is either `stream-null` or is an object of type `stream-pair`. An object of the `stream-pair` type contains a `stream-car` and 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-car` of a `stream-pair` is a promise that is forced the first time the `stream-car` is 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-car` is never accessed, the object stored there is never evaluated. Likewise, the `stream-cdr` is a promise to return a stream, and is only forced on demand.

## Stream API

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.

stream-type-tag [constant]

Symbol representing the `stream` type. The `type-for` procedure of library `(lispkit type)` returns this symbol for all stream objects.

stream-null [object]

`stream-null` is a stream that, when forced, is a single object, distinguishable from all other objects, that represents the null stream. `stream-null` is immutable and unique.

(stream? obj) [procedure]

Returns `#t` if obj is a stream; otherwise `#f` is returned.

(stream-null? obj) [procedure]

`stream-null?` is a procedure that takes an object obj and returns `#t` if the object is the distinguished null stream and `#f` otherwise. If object obj is a stream, `stream-null?` must force its promise in order to distinguish `stream-null` from `stream-pair`.

(stream-pair? obj) [procedure]

`stream-pair?` is a procedure that takes an object and returns `#t` if the object is a `stream-pair` constructed by `stream-cons` and `#f` otherwise. If object is a stream, `stream-pair?` must force its promise in order to distinguish `stream-null` from `stream-pair`.

(stream-cons obj strm) [syntax]

`stream-cons` is 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-pair` with the object in its `stream-car` and the stream in its `stream-cdr`. `stream-cons` must be syntactic, not procedural, because neither object obj nor stream is evaluated when `stream-cons` is called. Since `strm` is not evaluated, when the `stream-pair` is created, it is not an error to call `stream-cons` with a stream that is not of type stream; however, doing so will cause an error later when the `stream-cdr` of the `stream-pair` is accessed. Once created, a `stream-pair` is immutable.

    (define s (stream-cons 1 (stream-cons 2 (stream-cons 3 stream-null))))
    (stream-car s)               ⇒  1
    (stream-car (stream-cdr s))  ⇒  2

(stream-car strm) [procedure]

`stream-car` is a procedure that takes a stream strm and returns the object stored in the `stream-car` of the stream. `stream-car` signals an error if the object passed to it is not a `stream-pair`. Calling `stream-car` causes 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-cdr strm) [procedure]

`stream-cdr` is a procedure that takes a stream strm and returns the stream stored in the `stream-cdr` of the stream. `stream-cdr` signals an error if the object passed to it is not a `stream-pair`. Calling `stream-cdr` does not force the promise containing the stream stored in the `stream-cdr` of the stream.

(stream obj …) [syntax]

`stream` is syntax that takes zero or more objects obj and creates a newly-allocated stream containing in its elements the objects, in order. Since `stream` is 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 …) [syntax]

`stream-lambda` creates 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 `null` if 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

    (define stream-add
      (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 …) [syntax]

`define-stream` creates 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 `stream-lambda`. `define-stream` is syntactic sugar on `stream-lambda`.

(stream-let tag ((var val) …) expr1 expr2 …) [syntax]

`stream-let` creates 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-let` is evaluated, `stream-let` evaluates 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-let` provides syntactic sugar on `stream-lambda`, in the same manner as normal `let` provides syntactic sugar on normal `lambda`. However, unlike normal `let`, the `tag` is required, not optional, because unnamed `stream-let` is meaningless.

(display-stream strm) [procedure]
(display-stream strm n)
(display-stream strm n sep)
(display-stream strm n sep port)

`display-stream` displays 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->stream lst) [procedure]

`list->stream` takes 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->stream` is called, before the stream is created. If the list of objects is null, as in `(list->stream '())`, the null stream is returned.

(port->stream) [procedure]
(port->stream port)

`port->stream` takes 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-null`.

(stream->list strm) [procedure]
(stream->list strm n)

`stream->list` takes 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->list` will never return.

(stream-append strm …) [procedure]

`stream-append` returns 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 `x` is infinite, `(stream-append x y)` ≡ `x`.

(stream-concat strms) [procedure]

`stream-concat` takes 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 …) [procedure]

`stream-constant` takes 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) [procedure]

`stream-drop` returns 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-drop` returns the null stream.

(stream-drop-while pred? strm) [procedure]

`stream-drop-while` returns the suffix of the input stream that starts at the first element x for which `(pred?` x`)` is `#f`. The output stream shares structure with the input stream.

(stream-filter pred? strm) [procedure]

`stream-filter` returns a newly-allocated stream that contains only those elements x of the input stream for which `(pred?` x`)` is non-`#f`.

(stream-fold proc base strm) [procedure]

`stream-fold` applies 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-fold` when the end of the stream is reached. strm must be finite, or `stream-fold` will enter an infinite loop.

See also `stream-scan`, which is similar to `stream-fold`, but useful for infinite streams. `stream-fold` is a left-fold; there is no corresponding `right-fold`, since `right-fold` relies on finite streams that are fully-evaluated, at which time they may as well be converted to a list.

(stream-for-each proc strm …) [procedure]

`stream-for-each` applies a procedure proc elementwise to corresponding elements of the input streams strm … for its side-effects. `stream-for-each` stops as soon as any of its input streams is exhausted.

(stream-from first) [procedure]
(stream-from first delta)

`stream-from` creates 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-from` is frequently useful as a generator in `stream-of` expressions. See also `stream-range` for a similar procedure that creates finite streams.

(stream-iterate proc base) [procedure]

`stream-iterate` creates a newly-allocated stream containing base in its first element and applies proc to each element in turn to determine the succeeding element.

(stream-length strm) [procedure]

`stream-length` takes an input stream strm and returns the number of elements in the stream. It does not evaluate its elements. `stream-length` may only be used on finite streams as it enters an infinite loop with infinite streams.

(stream-map proc strm …) [procedure]

`stream-map` applies 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) …) [syntax]

`stream-match` provides 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-`#f` for 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 …) [syntax]

`stream-of` provides 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 `var`. `stream-from` and `stream-range` are frequently useful as generators.
- `(var is expr)`: Bind `var` to the value obtained by evaluating `expr`.
- `(pred? expr)`: Include in the output stream only those elements `x` for which `(pred? x)` is non-`#f`.

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) [procedure]
(stream-range first past delta)

`stream-range` creates 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 `-1` otherwise. First, past and step may be of any numeric type. `stream-range` is frequently useful as a generator in `stream-of` expressions.

(stream-ref strm n) [procedure]

`stream-ref` returns 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-reverse strm) [procedure]

`stream-reverse` returns a newly-allocated stream containing the elements of the input stream strm but in reverse order. `stream-reverse` may only be used with finite streams; it enters an infinite loop with infinite streams. `stream-reverse` does not force evaluation of the elements of the stream.

(stream-scan proc base strm) [procedure]

`stream-scan` accumulates 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 `i` elements of stream.

(stream-take strm n) [procedure]

`stream-take` takes 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) [procedure]

`stream-take-while` takes a predicate pred? and a stream strm and returns a newly-allocated stream containing those elements `x` that form the maximal prefix of the input stream for which `(pred? x)` is non-`#f`.

(stream-unfold mapper pred? generator base) [procedure]

`stream-unfold` is 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-`#f`.

(stream-unfolds proc seed) [procedure]

`stream-unfolds` returns n newly-allocated streams containing those elements produced by successive calls to the generator proc, which takes the current `seed` as 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 `proc` for the result stream
- `()`: the end of the result stream

It may require multiple calls of `proc` to produce the next element of any particular result stream.

(stream-zip strm …) [procedure]

`stream-zip` takes 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.