You are looking at historical revision 809 of this page. It may differ significantly from its current revision.

Introduction

The stream-ext egg provides many convenient extensions to work with srfi:40 streams.

Author

This egg is made by Alejandro Forero Cuervo <azul@freaks-unidos.net>.

Requires

License

The stream-ext egg for Chicken Scheme is in the public domain and may be reproduced or copied without permission from its author. Citation of the source is appreciated.

Constructors

stream-xcons

[procedure] (stream-xcons a b)

Of utility only as a value to be conveniently passed to higher-order procedures.

Examples:

(stream-xcons (stream 'b 'c) 'a)
=> #<stream (a b c)>

The name stands for "eXchanged CONS."

stream-cons*

[procedure] (stream-cons* a b)

Like stream, but the last argument provides the tail of the constructed stream, returning:

(stream-cons elt1 (stream-cons elt2 (stream-cons ... eltn)))

Examples:

(stream-cons* 1 2 3 (stream 4))
=> #<stream (1 2 3 4)>
(stream-cons* (stream 4))
=> #<stream (4)>

make-stream

[procedure] (make-stream n [fill])

Returns an n-element stream, whose elements are all the value fill. If the fill argument is not given, the elements of the stream may be arbitrary values.

(make-stream 4 'c)
=> <stream (c c c c)>

stream-tabulate

[procedure] (stream-tabulate n init-proc)

Returns an n-element list. Element i of the list, where 0 <= i < n, is produced by (init-proc i).

(stream-tabulate 4 identity)
=> #<stream (0 1 2 3)>

stream-iota

[procedure] (stream-iota a b)

Returns a list containing the elements:

(start start+step ... start+(count-1)*step)

The start and step parameters default to 0 and 1, respectively. This procedure takes its name from the APL primitive.

(stream-iota 5)
=> #<stream (0 1 2 3 4)>
(stream-iota 5 0 -0.1)
=> #<stream (0 -0.1 -0.2 -0.3 -0.4)>

stream-format

[procedure] (stream-format fmt ...)

Does the same as (format #f fmt ...), but returns the result as a stream of characters rather than a string.

stream-lines

[procedure] (stream-lines str)

Returns a stream with the lines found in the stream of characters str. Each line is itself returned as a stream of characters. It is an error if str contains elements that are not characters.

(stream-lines (stream #\h #\e #\y #\newline #\y #\o #\u))
=> #<stream (#<stream (#\h #\e #\y)> #<stream (#\y #\o #\u)>)>

Conversion

stream->list

[procedure] (stream->list str)

Returns a list with the elements in stream str. It is an error to pass an infinite stream.

list->stream

[procedure] (list->stream list)

Returns a stream with the elements in list list. The list might be circular (infinite), in which case the resulting stream will be infinite as well.

stream->string

[procedure] (stream->string str)

Returns a string with its characters read from the stream str. It is an error if str does not end or if it has elements than are not characters.

This function is the inverse of string->stream.

string->stream

[procedure] (string->stream str)

Returns a finite stream with the characters in the string str.

This function is the inverse of stream->string.

number->stream

[procedure] (number->stream str)

...

stream->number

[procedure] (stream->number str)

...

port->stream

[procedure] (port->stream [in [reader [close-at-eof]]])

Returns a stream with the contents of the input port in, which defaults to the current input port.

reader is a procedure. When called, it should read and return one element from the port passed as its only argument, advancing the read pointer (or return the eof object when no more elements are available in the port). The default value is read-char, which results in a stream of characters, but read and read-line can also be specified.

TODO: Documment close-at-eof.

iterator->stream

[procedure] (iterator->stream proc)

Turns an iterator into a stream. proc should be a procedure of two arguments. The first is a one-argument procedure that collects objects (adds them to an enumeration) and the second is a procedure of no arguments that can be used to stop iteration prematurely.

iterator->stream returns a stream. The iterator proc is only allowed to run as objects are read from the stream (with stream-car or stream-cdr).

Example:

(define (list->stream alist)
  (iterator->stream
    (lambda (collect stop)
      (for-each collect alist))))

Input and output

with-output-to-stream

[procedure] (with-output-to-stream proc)

Returns a stream of characters, which is built by calling proc, a procedure of no arguments, with its output port bound to a custom port. As characters are read from the stream (by stream-car or stream-cdr), proc is allowed to execute until it writes as many characters as required. For example, if the stream returned is immediately discarded, proc will not called at all.

(with-output-to-stream
  (lambda ()
    (format #t "Hey!~%")))
=> #<stream (#\H #\e #\y #\! #\newline)>

Remember that proc is only executed gradually, as the values from the stream are required. As a consequence, certain problems could arise by uncareful use of non-reentrant functions.

write-stream

[procedure] (write-stream stream [port [writer]])

Write all the elements in the stream stream to the output port port, which defaults to the current output port. If the stream is infinite, this function does not return.

writer is the procedure used to write individual elements to the port. It should receive the element to be written and the output port as its only arguments. The default value is write-char but write and write-line can also be used (depending on the contents of stream).

Predicates

stream=

[procedure] (stream= elt= str1 ...)

Determines stream equality, given an element-equality procedure. Stream A equals stream B if they are of the same length, and their corresponding elements are equal, as determined by elt=. If the element-comparison procedure's first argument is from stri, then its second argument is from stri+1, i.e. it is always called as (elt= a b) for a an element of stream A, and b an element of stream B.

In the n-ary case, every stri is compared to stri+1 (as opposed, for example, to comparing str1 to every stri, for i > 1). If there are no list arguments at all, stream= simply returns true.

The dynamic order in which the elt= procedure is applied to pairs of elements is not specified. For example, if stream= is applied to three lists, A, B, and C, it may first completely compare A to B, then compare B to C, or it may compare the first elements of A and B, then the first elements of B and C, then the second elements of A and B, and so forth.

The equality procedure must be consistent with eq?. That is, it must be the case that:

(eq? x y) => (elt= x y)

This implies that two lists which are eq? are always stream= as well; implementations may exploit this fact to "short-cut" the element-by-element comparisons.

(stream= eq?)
=> #t       ; Trivial cases
(stream= eq? (stream 0 1 2))
=> #t

stream-prefix=

[procedure] (stream-prefix= str prefix [=])

Evaluates whether the elements at the beginning of stream str are equal to the elements in the list prefix.

eq is the function used to compare the individual elements. The default is equal?.

If the prefix of the stream matches prefix, the function returns the contents of stream following it. False is returned otherwise.

(stream-prefix= (stream 1 2 3 4) '(1 2))
=> #<stream (3 4)>
(stream-prefix= (stream 1 2 3 4) '(1 3))
=> #f

Selectors

stream-caar ... stream-cddddr

[procedure] (stream-caar pair)
[procedure] (stream-cadr pair)
:
[procedure] (stream-cdddar pair)
[procedure] (stream-cddddr pair)

These procedures are compositions of stream-car and stream-cdr, where for example stream-caddr could be defined by:

(define (stream-caddr x) (stream-car (stream-cdr (stream-cdr x))))

Arbitrary compositions, up to four deep, are provided. There are twenty-eight of these procedures in all.

stream-ref

[procedure] (stream-ref str pos)

Returns the element in the stream str at the position pos. This is the same as the stream-car of (stream-drop str pos). It is an error if str has pos or fewer elements.

(stream-ref (stream 0 1 2 3 4 5) 3)
=> 3

stream-first ... stream-tenth

[procedure] (stream-first str)
[procedure] (stream-second str)
:
[procedure] (stream-ninth str)
[procedure] (stream-tenth str)

Synonyms for (stream-car str), (stream-cadr str), (stream-caddr str), ...

(stream-third (stream 0 1 2 3 4))
=> 2

stream-take

[procedure] (stream-take str count)

Returns a stream with the first count elements in stream str. It is an error if str has fewer than count elements.

(stream-take (stream 1 2 3 4 5) 2)
=> #<stream (1 2)>

stream-drop

[procedure] (stream-drop str count)

Returns the sub-stream of str obtained by omitting the first count elements. It is an error if list has fewer than count elements.

(stream-drop (stream 0 1 2 3 4 5) 3)
=> #<stream (3 4 5)>

stream-intersperse

[procedure] (stream-intersperse stream element)

Returns a new stream with the elements in the stream stream but placing element between each.

(stream-intersperse (stream 0 1 2 3) #f)
=> #<stream (0 #f 1 #f 2 #f 3)>
(stream-intersperse (stream 0) 1)
=> #<stream (0)>

stream-split

[procedure] (stream-split str pred)

Splits the stream str into multiple streams, removing the elements satisfying predicate pred. This is similar to what string-split does but operates on streams (rather than strings) and returns the result as a stream of streams (rather than a list of strings).

Example:

(stream-split (stream 1 2 3 5 7 8 9 10) even?)
=> #<stream (#<stream (1)> #<stream (3 5 7)> #<stream (9)>)>

stream-last

[procedure] (stream-last str)

Returns the last element of the non-empty finite stream str. It is an error to pass an empty stream.

(stream-last (stream 'a 'b 'c))
=> c

stream-last can be defined as:

(define (stream-last stream)
  (stream-car (stream-last-n stream 1)))

stream-last-n

[procedure] (stream-last-n stream count)

Returns a stream with the last count elements of the finite stream str. If fewer than count elements are available in stream, stream itself is returned.

(stream-null? (stream-last-n (stream #\a #\b #\c #\d) 0))
=> #t
(stream-last-n (stream #\a #\b #\c #\d) 1)
=> #<stream (#\d)>
(stream-last-n (stream #\a #\b #\c #\d) 3)
=> #<stream (#\b #\c #\d)>
(stream-last-n (stream #\a #\b #\c #\d) 20)
=> #<stream (#\a #\b #\c #\d)>

stream-butlast

[procedure] (stream-butlast stream)

Returns a stream with all the elements in the non-empty stream str except the last. The order of the elements is respected.

(stream-butlast (stream #\a #\b #\c))
=> #<stream (#\a #\b)>

stream-butlast can be defined as:

(define (stream-butlast stream)
  (stream-car (stream-butlast-n stream 1)))

stream-butlast-n

[procedure] (stream-butlast-n stream count)

Returns a stream with all the elements in the stream stream except the last count. The order of the elements is respected. It is an error if stream has fewer than count elements.

(stream-butlast-n (stream #\a #\b #\c) 2)
=> #<stream (#\a)>
(stream-null? (stream-butlast-n (stream #\a #\b #\c) 3))
=> #t

Miscellaneous: length, append, concatenate, reverse, zip & count

stream-length

[procedure] (stream-length str)

Returns the length of the argument stream (a non-negative integer n such that stream-cdr applied n times to the stream produces the null stream).

This function does not return when str is an infinite streams.

Returns the length of the stream str. This call does not return if str is an infinite stream.

(stream-length (stream 0 1 2 3))
=> 4

stream-length>=

[procedure] (stream-length>= str len)

Returns #t if the length of the stream str is greater or equal than len, #f otherwise.

For finite streams, this is equivalent, albeit faster, to:

(>= (stream-length str) len)

However, for infinite streams it is equivalent to #t (whereas the above code would never terminate).

stream-append

[procedure] (stream-append str1 str2 ...)

stream-append returns a stream consisting of the elements of str1 followed by the elements of the other stream parameters.

(stream-append (stream 1) (stream 2))
=> #<stream (1 2)>
(stream-append (stream 1) (stream 2 3 4))
=> #<stream (1 2 3 4)>
(stream-append (stream 'a '(b)) (stream '(c)))
=> #<stream (a (b) (c))>

stream-concatenate

[procedure] (stream-concatenate str)

...

stream-reverse

[procedure] (stream-reverse str)

stream-reverse returns a stream consisting of the elements of the stream str in reverse order.

This procedure does not return if str is an infinite stream.

(stream-reverse (stream 1 2 3))
=> #<stream (3 2 1)>
(stream-reverse (stream 'a '(b c) 'd '(e (f))))
=> #<stream ((e (f)) d (b c) a)>

stream-append-reverse

[procedure] (stream-append-reverse rev-head tail)

stream-append-reverse returns (stream-append (stream-reverse rev-head) tail). It is provided because it is a common operation -- a common list-processing style calls for this exact operation to transfer values accumulated in reverse order onto the front of another list, and because the implementation is significantly more efficient than the simple composition it replaces.

This procedure does not return if rev-head is an infinite stream.

stream-count

[procedure] (stream-count pred str1 str2 ...)

pred is a procedure taking as many arguments as there are streams and returning a single value. It is applied element-wise to the elements of the streams, and a count is tallied of the number of elements that produce a true value. This count is returned. count is "iterative" in that it is guaranteed to apply pred to the stream elements in a left-to-right order. The counting stops when the shortest list expires.

If all the streams are infinite, this procedure does not return.

(stream-count even? (stream 3 1 4 1 5 9 2 5 6))
=> 3
(stream-count < (stream 1 2 4 8) (stream 2 4 6 8 10 12 14 16))
=> 3
(stream-count < (stream 3 1 4 1) (make-stream #t 2))
=> 2

Filtering & Partitioning

stream-partition

[procedure] (stream-partition pred str)

Partitions the elements of stream str with predicate pred, and returns two values: the stream of in-elements and the stream of out-elements. The stream is not disordered -- elements occur in the result streams in the same order as they occur in the argument stream.

The dynamic order in which the various applications of pred depends on the evaluation of the streams. pred might be evaluated twice for each element in the argument stream.

(stream-partition symbol? (stream 'one 2 3 'four 'five 6))
=>
   #<stream (one four five)>
   #<stream (2 3 6)>

stream-remove

[procedure] (stream-remove pred str)

Returns a stream with all the elements in the stream str except those that satisfy predicate pred:

(lambda (pred str) (stream-filter (lambda (x) (not (pred x))) str))

The stream is not disordered -- elements that appear in the result list occur in the same order as they occur in the argument list.

(stream-remove even? (stream 0 7 8 8 43 -4))
=> #<stream (7 43)>

Searching

stream-find

[procedure] (stream-find pred str)

Return the first element of the stream str that satisfies predicate pred; false if no element does.

(stream-find even? (stream 3 1 4 1 5 9))
=> 4

Note that stream-find has an ambiguity in its lookup semantics -- if find returns #f, you cannot tell (in general) if it found a #f element that satisfied pred, or if it did not find any element at all. In many situations, this ambiguity cannot arise -- either the list being searched is known not to contain any #f elements, or the list is guaranteed to have an element satisfying pred. However, in cases where this ambiguity can arise, you should use stream-find-tail instead of stream-find -- stream-find-tail has no such ambiguity:

(cond ((stream-find-tail pred lis) => (lambda (pair) ...)) ; Handle (CAR PAIR)
      (else ...)) ; Search failed.

stream-find-tail

[procedure] (stream-find-tail pred str)

Returns the first stream-pair of str whose car satisfies predicate pred. If no pair does, returns false.

(stream-find-tail even? (stream 3 1 37 -8 -5 0 0))
=> #<stream (-8 -5 0 0)>
(stream-find-tail even? (stream 3 1 37 -5))
=> #f

stream-find-tail can be viewed as a general-predicate variant of the stream-member function. stream-member can be defined as a call to stream-find-tail:

;; (stream-member x str):
(stream-find-tail (lambda (elt) (equal? x elt)) str)

Find-tail is essentially stream-drop-while, where the sense of the predicate is inverted: Find-tail searches until it finds an element satisfying the predicate; drop-while searches until it finds an element that doesn't satisfy the predicate.

stream-take-while

[procedure] (stream-take-while pred str)

Returns the longest initial prefix of stream str whose elements all satisfy the predicate pred.

(stream-take-while even? (stream 2 18 3 10 22 9))
=> #<stream (2 18)>

stream-drop-while

[procedure] (stream-drop-while pred str)

Drops the longest initial prefix of stream str whose elements all satisfy the predicate pred and returns the rest of the stream.

(stream-drop-while even? (stream 2 18 3 10 22 9))
=> #<stream (3 10 22 9)>

stream-span, stream-break

[procedure] (stream-span pred str)
[procedure] (stream-break pred str)

stream-span splits the stream str into the longest initial prefix whose elements all satisfy predicate pred, and the remaining tail. stream-break inverts the sense of the predicate: the tail commences with the first element of the input list that satisfies the predicate.

In other words: stream-span finds the intial span of elements satisfying pred, and stream-break breaks the list at the first element not satisfying pred.

stream-span is equivalent to:

(values (stream-take-while pred str) (stream-drop-while pred str))

Examples:

(stream-span even? (stream 2 18 3 10 22 9))
=>
  #<stream (2 18)>
  #<stream (3 10 22 9)>
(stream-break even? (stream 3 1 4 1 5 9))
=>
  #<stream (3 1)>
  #<stream (4 1 5 9)>

stream-any

[procedure] (stream-any pred str1 str2 ...)

Applies the predicate pred across the streams str1 ... strn, returning true if the predicate returns true on any application.

If there are n stream arguments str1 ... strn, then pred must be a procedure taking n arguments and returning a boolean result.

stream-any applies pred to the first elements of the stri parameters. If this application returns a true value, stream-any immediately returns that value. Otherwise, it iterates, applying pred to the second elements of the stri parameters, then the third, and so forth. The iteration stops when a true value is produced or one of the streams runs out of values; in the latter case, stream-any returns #f.

Just like with any (see SRFI-1), it would be desirable to make the last call to pred a tail call. However, this would force stream-any to evaluate streams in advance. For this reason, the last call to pred is not a tail call.

Note the difference between stream-find and stream-any -- stream-find returns the element that satisfied the predicate; stream-any returns the true value that the predicate produced.

Like stream-every, stream-any's name does not end with a question mark -- this is to indicate that it does not return a simple boolean (#t or #f), but a general value.

(stream-any integer? (stream 'a 3 'b 2.7))
=> #t
(stream-any integer? (stream 'a 3.1 'b 2.7))
=> #f
(stream-any < (stream 3 1 4 1 5) (stream 2 7 1 8 2))
=> #t

stream-every

[procedure] (stream-every pred str1 str2 ...)

Applies the predicate across the streams, returning true if the predicate returns true on every application.

If there are n stream arguments str1 ... strn, then pred must be a procedure taking n arguments and returning a boolean result.

stream-every applies pred to the first elements of the stri parameters. If this application returns false, stream-every immediately returns false. Otherwise, it iterates, applying pred to the second elements of the stri parameters, then the third, and so forth. The iteration stops when a false value is produced or one of the lists runs out of values. In the latter case, every returns the true value produced by its final application of pred.

Just like with every (see SRFI-1), it would be desirable to make the last call to pred a tail call. However, this would force stream-every to evaluate streams in advance. For this reason, the last call to pred is not a tail call.

If one of the stri has no elements, every simply returns #t.

Like stream-any, stream-every's name does not end with a question mark -- this is to indicate that it does not return a simple boolean (#t or #f), but a general value.

stream-index

[procedure] (stream-index pred str1 str2 ...)

Return the index of the leftmost elements in the streams that satisfies predicate pred.

If there are n list arguments str1 ... strn, then pred must be a function taking n arguments and returning a boolean result.

stream-index applies pred to the first elements of the stri parameters. If this application returns true, stream-index immediately returns zero. Otherwise, it iterates, applying pred to the second elements of the stri parameters, then the third, and so forth. When it finds a tuple of list elements that cause pred to return true, it stops and returns the zero-based index of that position in the lists.

The iteration stops when one of the lists runs out of values; in this case, stream-index returns #f.

(stream-index even? (stream 3 1 4 1 5 9))
=> 2
(stream-index < (stream 3 1 4 1 5 9 2 5 6) (stream 2 7 1 8 2))
=> 1
(stream-index = (stream 3 1 4 1 5 9 2 5 6) (stream 2 7 1 8 2))
=> #f

stream-member, stream-memq, stream-memv

[procedure] (stream-member x str [=])
[procedure] (stream-memq x str)
[procedure] (stream-memv x str)

These procedures return the first substream of the stream str returned by (drop str i) for i less than the length of str whose stream-car is x. If x does not occur in str, then either #f is returned (for finite streams) or this call does not return. stream-memq uses eq? to compare x with the elements of str, while stream-memv uses eqv?, and stream-member uses equal?.

(stream-memq 'a (stream 'a 'b 'c))
=> (a b c)
(stream-memq 'b (stream 'a 'b 'c))
=> (b c)
(stream-memq 'a (stream 'b 'c 'd))
=> #f
(stream-memq (list 'a) (stream 'b '(a) 'c))
=> #f
(stream-member (list 'a) (stream 'b '(a) 'c))
=> ((a) c)
(stream-memq 101 (stream 100 101 102))
=> *unspecified*
(stream-memv 101 (stream 100 101 102))
=> (101 102)

stream-member allows the client to pass in an optional equality procedure = used to compare elements.

The comparison procedure is used to compare the elements ei of str to the element x in this way:

(= x ei) ; str is (E1 ...)

That is, the first argument is always x, and the second argument is one of the list elements. Thus one can reliably find the first element of str that is greater than five with (stream-member 5 list <).

Note that fully general list searching may be performed with the stream-find-tail and stream-find procedures, e.g.

; Find the first pair with an even stream-car:
(stream-find-tail even? str)

Deletion

stream-delete

[procedure] (stream-delete x str [=])

stream-delete returns a stream identical to str but removing all occurences of the element x. The comparison procedure =, which defaults to equal?, is used to find them.

The stream is not disordered -- elements that appear in the result stream occur in the same order as they occur in the argument stream.

Note that fully general element deletion can be performed with the stream-remove procedure, e.g.:

;; Delete all the even elements from STR:
(stream-remove even? str)

The comparison procedure is used in this way: (= x ei). That is, x is always the first argument, and a element from the stream is always the second argument. Thus, one can reliably remove all the numbers greater than five from a stream with (delete 5 stream <).

stream-delete-duplicates

[procedure] (stream-delete-duplicates str [=])

stream-delete-duplicates removes duplicate elements from the str stream argument. If there are multiple equal elements in the argument stream, the result stream only contains the first or leftmost of these elements in the result. The order of these surviving elements is the same as in the original stream -- stream-delete-duplicates does not disorder the stream.

The = parameter is used to compare the elements of the list; it defaults to equal?. If x comes before y in list, then the comparison is performed (= x y). The comparison procedure will be used to compare each pair of elements in list no more than once; the order in which it is applied to the various pairs is not specified.

Be aware that, in general, stream-delete-duplicates runs in time O(n2) for n-streams lists. Uniquifying long lists can be accomplished in O(n lg n) time by sorting the stream to bring equal elements together, then using a linear-time algorithm to remove equal elements. Alternatively, one can use algorithms based on element-marking, with linear-time results.

Also note that a list might be kept in memory with the entire contents of the stream during the execution of calls to this function.

(stream-delete-duplicates (stream 0 1 0 3 0 1 3 4))
=> #<stream (0 1 3 4)>

Version History

1.4
Add stream-downcase, stream-upcase, vector->stream, stream->vector, stream-sort, stream-unlines, stream<, stream>, make-infinite-stream, stream-fold, stream-fold-right and stream-fold-right-delay. Made make-stream and stream-tabulate receive an optional tail argument. Many bug fixes.
1.3.1
Replaced use of (end-of-file) with #!eof
1.3 (r2136)
Made stream-reverse accept an optional parameter: the end of the list. Made all parameters to stream->port optional (the port now defaults to the current input port). Fixed stream-every. Added stream->symbol, symbol->stream, stream-drop-safe and stream-take-safe.
1.2 (r1122)
Added list->stream, number->stream, stream->number, stream-intersperse, stream-last-n, stream-butlast, stream-butlast-n, iterator->stream, call-with-output-stream and call-with-input-stream; and fixed stream-delete-duplicates, stream-find and stream-find-tail.
1.1
Removed stream-filter (it's provided by srfi-40).
1.0
First public release.