# (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** 
Symbol representing the `stream` type. The `type-for` procedure of library `(lispkit type)` returns this symbol for all stream objects.
**stream-null** 
`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*****)** 
Returns `#t` if *obj* is a stream; otherwise `#f` is returned.
**(stream-null? *****obj*****)**
`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*****)**
`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*****)** 
`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.
```scheme
(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*****)**
`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*****)**
`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 ...*****)**
`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 ...*****)**
`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.
```scheme
(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 ...*****)**
`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 ...*****)**
`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*****)** \
\&#xNAN;**(display-stream *****strm n*****)**\
\&#xNAN;**(display-stream *****strm n sep*****)**\
\&#xNAN;**(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*****)**
`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)** \
\&#xNAN;**(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*****)** \
\&#xNAN;**(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 ...*****)**
`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*****)**
`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 ...*****)**
`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*****)**
`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*****)**
`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*****)**
`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*****)**
`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 ...*****)**
`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*****)** \
\&#xNAN;**(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*****)**
`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*****)**
`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 ...*****)**
`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) ...*****)**
`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 ...*****)**
`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*****)** \
\&#xNAN;**(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*****)**
`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*****)**
`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*****)**
`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*****)**
`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*****)**
`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*****)**
`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*****)**
`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 ...*****)**
`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.
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://www.lisppad.app/libraries/lispkit/lispkit-stream.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.