• Wiki
• Download
• Manual
• Eggs
• API
• Tests
• Bugs

Outdated egg!

This is an egg for CHICKEN 3, the unsupported old release. You're almost certainly looking for the CHICKEN 4 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

• eggs

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>.

;; $Id: stream-ext.scm 5600 2006-05-19 20:01:00Z azul $
;;
;; This file is in the public domain and may be reproduced or copied without
;; permission from its author.  Citation of the source is appreciated.
;;
;; Alejandro Forero Cuervo <azul@freaks-unidos.net>
;;
;; This file implements an egg for Chicken Scheme that contains useful
;; extensions to work with streams as defined in srfi-40.
;;
;; Documentation is available in HTML format.
;;
;; Newer versions might be available at:
;;
;;    http://wiki.call-cc.org/stream-ext

Requires

• srfi-40
• format-modular

(require-extension srfi-40 srfi-1 format-modular)

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 stream object)

Creates a stream prepending object to stream. The name stands for "eXchanged CONS."

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

(stream-xcons (stream 2 3) 1)
 => ;; Equivalent to (stream 1 2 3)

(stream-xcons (stream 2 3 4) 1)
 => ;; Equivalent to (stream 1 2 3 4)

(define (stream-xcons stream object) (stream-cons object stream))

stream-cons*

[procedure] (stream-cons* [elt1 ...] tail)

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

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

(stream-cons* 1 2 3 (stream 4))
 => ;; Equivalent to (stream 1 2 3 4)

(stream-cons* (stream 4))
 => ;; Equivalent to (stream 4)

(define (stream-cons* . elts)
  (stream-delay
   (if (null? (cdr elts))
     (car elts)
     (stream-cons (car elts) (apply stream-cons* (cdr elts))))))

</procedure>

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 0)
 => ;; Equivalent to (stream 0 0 0 0)

(define (make-stream n . rest)
  (let-optionals rest ((obj #f) (tail stream-null))
    (stream-tabulate n (constantly obj) tail)))

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 (lambda (x) (* x x)))
 => ;; Equivalent to (stream 0 4 9 16)

(define (stream-tabulate n init-proc . rest)
  (assert (number? n))
  (assert (not (negative? n)))
  (let-optionals rest ((tail stream-null))
    (let loop ((i 0))
      (stream-delay
        (if (equal? i n)
          tail
          (stream-cons (init-proc i) (loop (+ i 1))))))))

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)
 => ;; Equivalent to (stream 0 1 2 3 4)

(stream-iota 5 0 -0.1)
 => ;; Equivalent to (stream 0 -0.1 -0.2 -0.3 -0.4)

(define (stream-iota count . args)
  (let loop ((i count)
             (start (if (null? args) 0 (car args)))
             (step (if (or (null? args) (null? (cdr args))) 1 (cadr args))))
    (stream-delay
      (if (zero? i)
        stream-null
        (stream-cons start (loop (- i 1) (+ start step) step))))))

make-infinite-stream

TODO: Document

(define (make-infinite-stream proc start)
  (stream-delay
    (let ((next (proc start)))
      (stream-cons next (make-infinite-stream proc next)))))

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.

(define (stream->list str)
  (if (stream-null? str)
    '()
    (cons (stream-car str) (stream->list (stream-cdr str)))))

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.

(define (list->stream list)
  (stream-delay
    (if (null? list)
      stream-null
      (stream-cons (car list) (list->stream (cdr list))))))

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.

(define stream->string (compose list->string stream->list))

string->stream

[procedure] (string->stream str [tail])

Returns a finite stream with the characters in the string str. tail, which defaults to stream-null, is appended at the end.

With tail set to stream-null, this function is the inverse of stream->string.

(define (string->stream str . rest)
  (let-optionals rest ((tail stream-null))
    (let loop ((i 0))
      (stream-delay
       (if (equal? i (string-length str))
           tail
           (stream-cons (string-ref str i) (loop (+ i 1))))))))

number->stream

[procedure] (number->stream str)

...

(define number->stream (compose string->stream number->string))

stream->number

[procedure] (stream->number str)

...

(define stream->number (compose string->number stream->string))

stream->vector

[procedure] (stream->vector str)

...

(define stream->vector (compose list->vector stream->list))

vector->stream

[procedure] (vector->stream str)

...

(define vector->stream (compose list->stream vector->list))

stream->symbol

[procedure] (stream->symbol str)

...

(define stream->symbol (compose string->symbol stream->string))

symbol->stream

[procedure] (symbol->stream str)

...

(define symbol->stream (compose string->stream symbol->string))

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.

close-at-eof, which defaults to close-input-port, will be called as soon as an end of file object is read from the port. A common idiom is to use:

(port->stream (open-input-file path))

This will case the file to be closed as soon as the entire input is consumed. However, the caller must be careful to actually read the entire stream before discarding it or file descriptors will be leaked.

(define (port->stream . rest)
  (let-optionals rest ((in (current-input-port)) (reader read-char) (close-at-eof close-input-port))
    (stream-delay
      (let ((element (reader in)))
        (cond
          ((eof-object? element) (when close-at-eof (close-at-eof in)) stream-null)
          (else (stream-cons element (port->stream in reader 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))))

(define (iterator->stream proc)
  (stream-delay
    (call-with-current-continuation
      (lambda (return)
        (proc
          (lambda (obj)
            (call-with-current-continuation
              (lambda (next)
                (return
                  (stream-cons obj
                    (stream-delay
                      (call-with-current-continuation
                        (lambda (new)
                          (set! return new)
                          (next #t)))))))))
          (lambda () (return stream-null)))
        (return stream-null)))))

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 "hi")))
 => ;; Equivalent to (stream #\h #\i)

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.

(define (with-output-to-stream proc)
  (iterator->stream
    (lambda (write close)
      (with-output-to-port
        (make-output-port
          (lambda (string)
            (let loop ((i 0))
              (when (< i (string-length string))
                (write (string-ref string i))
                (loop (+ i 1)))))
          close)
        proc))))

with-input-from-stream

[procedure] (with-input-from-stream stream proc)

Calls the procedure proc with no arguments, with its current-input-port bound to a port created from the stream of characters stream.

(with-input-from-stream (stream #\" #\a #\b #\c #\") read)
 => "abc"

The stream will only be evaluated as the input is consumed by the procedure.

(define (with-input-from-stream stream proc)
  (with-input-from-port
    (make-input-port
      (lambda ()
        (if (stream-null? stream)
          #!eof
          (let ((char (stream-car stream)))
            (set! stream (stream-cdr stream))
            char)))
      (lambda ()
        (not (stream-null? stream)))
      (lambda ()
        (set! stream stream-null))
      (lambda ()
        (stream-car stream)))
    proc))

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).

(define (write-stream stream . rest)
  (let-optionals rest ((port (current-output-port)) (writer write-char))
    (let loop ((s stream))
      (unless (stream-null? s)
        (writer (stream-car s) port)
        (loop (stream-cdr s))))))

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

(define (stream= elt= . strs)
  (or (every stream-null? strs)
      (and (not (any stream-null? strs))
           (let loop ((es (map stream-car strs)))
             (or (null? (cdr es))
                 (and (elt= (car es) (cadr es)) (loop (cdr es)))))
           (apply stream= elt= (map stream-cdr strs)))))

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

(define (stream-prefix= str prefix . rest)
  (if (null? prefix)
    str
    (and (not (stream-null? str))
         ((if (null? rest) equal? (car rest)) (stream-car str) (car prefix))
         (apply stream-prefix= (stream-cdr str) (cdr prefix) rest))))

stream>, stream<

...

(define (stream< elt< . strs)
  (or (null? strs)
      (null? (cdr strs))
      (and
        (let loop ((a (car strs)) (b (cadr strs)))
          (or (elt< (stream-car a) (stream-car b))
              (and (not (elt< (stream-car b) (stream-car a)))
                   (loop (stream-cdr a) (stream-cdr b)))))
        (apply stream< elt (cdr strs)))))

(define (stream> elt< . strs) (apply stream< (complement elt<) strs))

Selectors

stream-caar ... stream-cddddr

[procedure] (stream-caar stream)
[procedure] (stream-cadr stream)
[procedure] (stream-cdar stream)
[procedure] (stream-cddr stream)
[procedure] (stream-caaar stream)
[procedure] (stream-caadr stream)
[procedure] (stream-cadar stream)
[procedure] (stream-caddr stream)
[procedure] (stream-cdaar stream)
[procedure] (stream-cdadr stream)
[procedure] (stream-cddar stream)
[procedure] (stream-cdddr stream)
[procedure] (stream-caaaar stream)
[procedure] (stream-caaadr stream)
[procedure] (stream-caadar stream)
[procedure] (stream-caaddr stream)
[procedure] (stream-cadaar stream)
[procedure] (stream-cadadr stream)
[procedure] (stream-caddar stream)
[procedure] (stream-cadddr stream)
[procedure] (stream-cdaaar stream)
[procedure] (stream-cdaadr stream)
[procedure] (stream-cdadar stream)
[procedure] (stream-cdaddr stream)
[procedure] (stream-cddaar stream)
[procedure] (stream-cddadr stream)
[procedure] (stream-cdddar stream)
[procedure] (stream-cddddr stream)

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.

(define stream-caar   (compose stream-car stream-car))
(define stream-cadr   (compose stream-car stream-cdr))
(define stream-cdar   (compose stream-cdr stream-car))
(define stream-cddr   (compose stream-cdr stream-cdr))

(define stream-caaar  (compose stream-caar stream-car))
(define stream-caadr  (compose stream-caar stream-cdr))
(define stream-cadar  (compose stream-cadr stream-car))
(define stream-caddr  (compose stream-cadr stream-cdr))
(define stream-cdaar  (compose stream-cdar stream-car))
(define stream-cdadr  (compose stream-cdar stream-cdr))
(define stream-cddar  (compose stream-cddr stream-car))
(define stream-cdddr  (compose stream-cddr stream-cdr))

(define stream-caaaar (compose stream-caaar stream-car))
(define stream-caaadr (compose stream-caaar stream-cdr))
(define stream-caadar (compose stream-caadr stream-car))
(define stream-caaddr (compose stream-caadr stream-cdr))
(define stream-cadaar (compose stream-cadar stream-car))
(define stream-cadadr (compose stream-cadar stream-cdr))
(define stream-caddar (compose stream-caddr stream-car))
(define stream-cadddr (compose stream-caddr stream-cdr))
(define stream-cdaaar (compose stream-cdaar stream-car))
(define stream-cdaadr (compose stream-cdaar stream-cdr))
(define stream-cdadar (compose stream-cdadr stream-car))
(define stream-cdaddr (compose stream-cdadr stream-cdr))
(define stream-cddaar (compose stream-cddar stream-car))
(define stream-cddadr (compose stream-cddar stream-cdr))
(define stream-cdddar (compose stream-cdddr stream-car))
(define stream-cddddr (compose stream-cdddr stream-cdr))

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

(define (stream-ref str pos)
  (if (zero? pos)
      (stream-car str)
      (stream-ref (stream-cdr str) (- pos 1))))

stream-first ... stream-tenth

[procedure] (stream-first str)
[procedure] (stream-second str)
[procedure] (stream-third str)
[procedure] (stream-fourth str)
[procedure] (stream-fifth str)
[procedure] (stream-sixth str)
[procedure] (stream-seventh str)
[procedure] (stream-sixth str)
[procedure] (stream-eighth 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

(define stream-first   stream-car)
(define stream-second  stream-cadr)
(define stream-third   stream-caddr)
(define stream-fourth  stream-cadddr)
(define stream-fifth   (compose stream-car    stream-cddddr))
(define stream-sixth   (compose stream-cadr   stream-cddddr))
(define stream-seventh (compose stream-caddr  stream-cddddr))
(define stream-eighth  (compose stream-cadddr stream-cddddr))
(define stream-ninth   (compose stream-car    stream-cddddr stream-cddddr))
(define stream-tenth   (compose stream-cadr   stream-cddddr stream-cddddr))

stream-take, stream-take-safe

[procedure] (stream-take str count)
[procedure] (stream-take-safe str count)

Returns a stream with the first count elements in stream str. For stream-take, it is an error if str has fewer than count elements; for stream-take-safe, str will be returned.

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

(define (stream-take stream count)
  (stream-delay
   (if (zero? count)
       stream-null
       (stream-cons (stream-car stream)
                    (stream-take (stream-cdr stream) (- count 1))))))

(define (stream-take-safe stream count)
  (stream-delay
    (if (or (zero? count) (stream-null? stream))
      stream-null
      (stream-cons (stream-car stream)
                   (stream-take-safe (stream-cdr stream) (- count 1))))))

stream-drop, stream-drop-safe

[procedure] (stream-drop str count)
[procedure] (stream-drop-safe str count)

Returns the sub-stream of str obtained by omitting the first count elements. For stream-drop, it is an error if {str}} has fewer than count elements; for stream-drop-safe, the empty stream will be returned.

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

(define (stream-drop str count)
  (stream-delay
   (if (zero? count)
       str
       (stream-drop (stream-cdr str) (- count 1)))))

(define (stream-drop-safe str count)
  (stream-delay
    (if (or (zero? count) (stream-null? str))
      str
      (stream-drop-safe (stream-cdr str) (- count 1)))))

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)>

(define (stream-intersperse stream element . rest)
  (let-optionals rest ((tail stream-null))
    (stream-delay
      (if (stream-null? stream)
        tail
        (stream-cons (stream-car stream)
          (let loop ((rest (stream-cdr stream)))
            (if (stream-null? rest)
              tail
              (stream-cons element (stream-cons (stream-car rest) (loop (stream-cdr rest)))))))))))

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)>)>

(define (stream-split in p?)
  (let loop ((current '()) (s in))
    (stream-delay
      (cond
        ((stream-null? s)
           (if (null? current)
             stream-null
             (stream-cons (list->stream (reverse current)) stream-null)))
        ((p? (stream-car s))
           (stream-cons (list->stream (reverse current)) (loop '() (stream-cdr s))))
        (else (loop (cons (stream-car s) current) (stream-cdr s)))))))

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 could be defined as:

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

(define (stream-last str)
  (if (stream-null? (stream-cdr str))
    (stream-car str)
    (stream-last (stream-cdr str))))

stream-last-n

<rocedure>(stream-last-n stream count)</procedure>

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)>

(define (stream-last-n str count)
  (stream-delay
    (let ((l (list #f)))
      (set-cdr! l l)
      (let loop ((s str) (l l) (i 0))
        (cond
          ((stream-null? s)
           (if (< i count)
             str
             (stream-take (list->stream (cdr l)) i)))
          ((equal? i count)
             (set-car! l (stream-car s))
             (loop (stream-cdr s) (cdr l) i))
          (else
            (set-car! l (stream-car s))
            (set-cdr! l (cons i (cdr l)))
            (loop (stream-cdr s) (cdr l) (+ i 1))))))))

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 str)
  (stream-butlast-n str 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

(define (stream-butlast-n str count)
  (stream-delay
    (let loop ((head str) (tail (stream-drop str count)))
      (if (stream-null? tail)
        stream-null
        (stream-cons (stream-car head) (loop (stream-cdr head) (stream-cdr tail)))))))

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

(define (stream-length str)
  (let loop ((i 0) (s str))
    (if (stream-null? s)
        i
        (loop (+ i 1) (stream-cdr s)))))

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 (specially when len is significantly smaller than the length of str), to:

(>= (stream-length str) len)

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

(define (stream-length>= str len)
  (or (zero? len)
      (and (not (stream-null? str))
           (stream-length>= (stream-cdr str) (- len 1)))))

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))>

(define (stream-append . strs)
  (stream-delay
    (cond
      ((null? strs) stream-null)
      ((null? (cdr strs)) (car strs))
      (else
        (let loop ((c (car strs)) (rest (cdr strs)))
          (stream-delay
            (if (stream-null? c)
              (apply stream-append rest)
              (stream-cons (stream-car c) (loop (stream-cdr c) rest)))))))))

stream-concatenate

[procedure] (stream-concatenate str)

...

(define (stream-concatenate strs)
  (stream-delay
    (if (stream-null? strs)
      stream-null
      (stream-append (stream-car strs) (stream-concatenate (stream-cdr strs))))))

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)>

(define (stream-reverse str . args)
  (stream-delay
    (let-optionals args ((tail stream-null))
      (let loop ((head str) (tail tail))
        (if (stream-null? head) 
          tail
          (loop (stream-cdr head) (stream-cons (stream-car head) tail)))))))

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

(define (stream-count pred . strs)
  (apply
    stream-fold
    (lambda args
      (+ (last args)
         (if (apply pred (butlast args)) 1 0)))
    0
    strs)

Fold

stream-fold

...

(define (stream-fold func nil . strs)
  (if (any stream-null? str)
    nil
    (apply
      stream-fold
      func
      (apply (cut func <...> nil) (map stream-car strs))
      (map stream-cdr strs))))

stream-fold-right

...

(define (stream-fold-right func nil str)
  (if (stream-null? str)
    nil
    (func (stream-car str) (stream-fold-right func nil (stream-cdr str)))))

stream-fold-right-delay

...

Similar to stream-fold-right, but useful when the result of the folding procedure is a stream; in this case, the evaluation of the fold is done in a lazy manner.

(define (stream-fold-right-delay func nil str)
  (stream-delay
    (if (stream-null? str)
      nil
      (func (stream-car str) (stream-fold-right-delay func nil (stream-cdr str))))))

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)>

(define (stream-partition pred str)
  (values (stream-filter pred str)
          (stream-remove pred str)))

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)>

(define (stream-remove pred str)
  (stream-filter (complement pred) str))

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.

(define (stream-find pred str)
  (let ((result (stream-find-tail pred str)))
    (and result (stream-car result))))

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.

(define (stream-find-tail pred str)
  (and (not (stream-null? str))
       (if (pred (stream-car str))
           str
           (stream-find-tail pred (stream-cdr str)))))

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)>

(define (stream-take-while pred str)
  (stream-delay
   (if (or (stream-null? str) (not (pred (stream-car str))))
       stream-null
       (stream-cons (stream-car str)
         (stream-take-while pred (stream-cdr str))))))

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)>

(define (stream-drop-while pred str)
  (stream-delay
   (if (or (stream-null? str) (not (pred (stream-car str))))
       str
       (stream-drop-while pred (stream-cdr str)))))

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)>

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

(define (stream-break pred str)
  (stream-span (complement pred) str))

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

(define (stream-any pred . strs)
  (and (not (find stream-null? strs))
       (or (apply pred (map stream-car strs))
           (apply stream-any pred (map stream-cdr strs)))))

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.

(define (stream-every pred . strs)
  (let loop ((strs strs))
    (or (find stream-null? strs)
        (and (apply pred (map stream-car strs))
             (loop (map stream-cdr strs))))))

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

(define (stream-index pred . strs)
  (let loop ((strs strs) (pos 0))
    (and (not (find stream-null? strs))
         (if (apply pred (map stream-car strs))
             pos
             (loop (map stream-cdr strs) (+ pos 1))))))

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 stream 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)

(define (stream-member-real x str =)
  (stream-find-tail (cut = x <>) str))

(define (stream-member x str . rest)
  (stream-member-real x str (if (null? rest) equal? (car rest))))

(define stream-memq (cut stream-member-real <...> eq?))
(define stream-memv (cut stream-member-real <...> eqv?))

Sorting

stream-sort

[procedure] (stream-sort str <)

Returns a copy of str with its elements sorted.

We don't care about the slowness of converting to a list and then back to a stream since

• The entire set of elements will be needed in memory and
• Sort has greater algorithmical complexity O(N) = N*log(N) than the conversions.

(define (stream-sort stream ord)
  (list->stream (sort (stream->list stream) ord)))

Strings as streams

stream-downcase, stream-upcase

[procedure] (stream-downcase str)
[procedure] (stream-upcase str)

Returns a stream identical to the stream of characters str but with all characters converted to lowercase or uppercase.

(define stream-downcase (cut stream-map char-downcase <>))
(define stream-upcase   (cut stream-map char-upcase   <>))

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.

(define (stream-format fmt . rest)
  (with-output-to-stream
    (lambda ()
      (format #f fmt rest))))

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)>)>

(define stream-lines (cut stream-split <> (cut equal? <> #\newline)))

stream-unlines

TODO: Document

(define (stream-unlines lines)
  (stream-concatenate (stream-intersperse lines (stream #\newline))))

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 <).

(define (stream-delete x str . rest)
  (stream-remove
    (let ((= (if (null? rest) equal? (car rest))))
      (lambda (elt) (= x elt)))
    str))

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)>

(define (stream-delete-duplicates str . rest)
  (stream-delete-dups str '() (if (null? rest) equal? (car rest))))

(define (stream-delete-dups str already =)
  (stream-delay
    (cond
      ((stream-null? str) stream-null)
      ((any (lambda (x) (= x (stream-car str))) already)
       (stream-delete-dups (stream-cdr str) already =))
      (else
        (stream-cons (stream-car str)
                     (stream-delete-dups (stream-cdr str) (cons (stream-car str) already) =))))))

Other undocumented code

The following procedures are also provided.

TODO: Move them to the appropriate sections in this document and get rid of this section.

(define (stream-convert-safe check? convert)
  (lambda (obj)
    (if (check? obj)
      (convert obj)
      obj)))

(define (stream-wrap-proc-generic convert-inputs convert-outputs)
  (lambda (proc)
    (lambda args
      (receive results
               (apply proc (map convert-inputs args))
        (apply values (map convert-outputs results))))))

(define stream-wrap-proc-string
  (stream-wrap-proc-generic
    (stream-convert-safe stream? stream->string)
    (stream-convert-safe string? string->stream)))

(define stream-wrap-proc-list
  (stream-wrap-proc-generic
    (stream-convert-safe stream? stream->list)
    (stream-convert-safe list? list->stream)))

(define stream-wrap-proc-stream
  (stream-wrap-proc-generic
    (lambda (obj)
      (cond
        ((list? obj) (list->stream obj))
        ((string? obj) (string->stream obj))
        (else obj)))
    identity))

;;; Pattern Matching

(define (stream-grep re stream)
  (let ((real-re (if (string? re) (regexp re) re)))
    (stream-filter (cut string-match real-re <>) stream)))

; (equal? tail stream-null) rather than (stream-null? tail) to avoid an
; off-by-one error (evaluating tail before obj is fully consumed).

(define (->stream-char obj . rest)
  (stream-delay
   (let-optionals rest ((tail stream-null))
     (cond
      ((string? obj) (string->stream obj tail))
      ((or (number? obj) (boolean? obj) (symbol? obj)) (->stream-char (->string obj) tail))
      ((char? obj) (stream-cons obj tail))
      ((port? obj) (port->stream obj))
      ((stream? obj)
       (if (equal? tail stream-null)
           obj
           (stream-append obj tail)))
      (else (error "Unable to convert object to stream-char" obj))))))

(define (stream-replace in reps)
  (if (stream-null? in)
      stream-null
      (let ((obj (assoc (stream-car in) reps)))
        (if obj
            (->stream-char (cadr obj) (stream-replace (stream-cdr in) reps))
            (stream-cons (stream-car in) (stream-replace (stream-cdr in) reps))))))

(define (stream-translate str from to)
  (stream-map (lambda (c) (if (equal? c from) to c)) str))

Version History

1.6

Added stream-wrap-proc-string, stream-wrap-proc-list and stream-wrap-proc-stream to simplify integration of streams-using code with non-streams-using code.

1.5

Build script now uses exports.

1.4.1

Small bug fix in stream-fold-right.

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.