1 ;;;; streams.scm --- general lazy streams
4 ;;;; Copyright (C) 1999, 2001, 2004, 2006 Free Software Foundation, Inc.
6 ;;;; This library is free software; you can redistribute it and/or
7 ;;;; modify it under the terms of the GNU Lesser General Public
8 ;;;; License as published by the Free Software Foundation; either
9 ;;;; version 2.1 of the License, or (at your option) any later version.
11 ;;;; This library is distributed in the hope that it will be useful,
12 ;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
13 ;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 ;;;; Lesser General Public License for more details.
16 ;;;; You should have received a copy of the GNU Lesser General Public
17 ;;;; License along with this library; if not, write to the Free Software
18 ;;;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 ;; the basic stream operations are inspired by
21 ;; (i.e. ripped off) Scheme48's `stream' package,
22 ;; modulo stream-empty? -> stream-null? renaming.
24 (define-module (ice-9 streams)
26 stream-car stream-cdr stream-null?
27 list->stream vector->stream port->stream
28 stream->list stream->reversed-list
29 stream->list&length stream->reversed-list&length
31 stream-fold stream-for-each stream-map))
35 ;; (make-stream producer initial-state)
36 ;; - PRODUCER is a function of one argument, the current state.
37 ;; it should return either a pair or an atom (i.e. anything that
38 ;; is not a pair). if PRODUCER returns a pair, then the car of the pair
39 ;; is the stream's head value, and the cdr is the state to be fed
40 ;; to PRODUCER later. if PRODUCER returns an atom, then the stream is
41 ;; considered depleted.
43 ;; (stream-car stream)
44 ;; (stream-cdr stream)
45 ;; (stream-null? stream)
48 ;; (list->stream list)
49 ;; (vector->stream vector)
50 ;; - make a stream with the same contents as LIST/VECTOR.
52 ;; (port->stream port read)
53 ;; - makes a stream of values which are obtained by READing from PORT.
55 ;; (stream->list stream)
56 ;; - returns a list with the same contents as STREAM.
58 ;; (stream->reversed-list stream)
59 ;; - as above, except the contents are in reversed order.
61 ;; (stream->list&length stream)
62 ;; (stream->reversed-list&length stream)
63 ;; - multiple-valued versions of the above two, the second value is the
64 ;; length of the resulting list (so you get it for free).
66 ;; (stream->vector stream)
69 ;; (stream-fold proc init stream0 ...)
70 ;; - PROC must take (+ 1 <number-of-stream-arguments>) arguments, like this:
71 ;; (PROC car0 ... init). *NOTE*: the INIT argument is last, not first.
72 ;; I don't have any preference either way, but it's consistent with
73 ;; `fold[lr]' procedures from SRFI-1. PROC is applied to successive
74 ;; elements of the given STREAM(s) and to the value of the previous
75 ;; invocation (INIT on the first invocation). the last result from PROC
78 ;; (stream-for-each proc stream0 ...)
79 ;; - like `for-each' we all know and love.
81 ;; (stream-map proc stream0 ...)
82 ;; - like `map', except returns a stream of results, and not a list.
86 (define (make-stream m state)
91 (make-stream m (cdr o)))
94 (define (stream-car stream)
95 "Returns the first element in STREAM. This is equivalent to `car'."
98 (define (stream-cdr stream)
99 "Returns the first tail of STREAM. Equivalent to `(force (cdr STREAM))'."
100 (cdr (force stream)))
102 (define (stream-null? stream)
103 "Returns `#t' if STREAM is the end-of-stream marker; otherwise
104 returns `#f'. This is equivalent to `null?', but should be used
105 whenever testing for the end of a stream."
106 (null? (force stream)))
108 (define (list->stream l)
109 "Returns a newly allocated stream whose elements are the elements of
110 LIST. Equivalent to `(apply stream LIST)'."
115 (define (vector->stream v)
117 (let ((len (vector-length v)))
120 (cons (vector-ref v i) (+ 1 i)))))
123 (define (stream->reversed-list&length stream)
124 (let loop ((s stream) (acc '()) (len 0))
127 (loop (stream-cdr s) (cons (stream-car s) acc) (+ 1 len)))))
129 (define (stream->reversed-list stream)
131 (lambda () (stream->reversed-list&length stream))
134 (define (stream->list&length stream)
136 (lambda () (stream->reversed-list&length stream))
137 (lambda (l len) (values (reverse! l) len))))
139 (define (stream->list stream)
140 "Returns a newly allocated list whose elements are the elements of STREAM.
141 If STREAM has infinite length this procedure will not terminate."
142 (reverse! (stream->reversed-list stream)))
144 (define (stream->vector stream)
146 (lambda () (stream->reversed-list&length stream))
148 (let ((v (make-vector len)))
149 (let loop ((i 0) (l l))
152 (vector-set! v (- len i 1) (car l))
153 (loop (+ 1 i) (cdr l)))))
156 (define (stream-fold f init stream . rest)
157 (if (null? rest) ;fast path
158 (stream-fold-one f init stream)
159 (stream-fold-many f init (cons stream rest))))
161 (define (stream-fold-one f r stream)
162 (if (stream-null? stream)
164 (stream-fold-one f (f (stream-car stream) r) (stream-cdr stream))))
166 (define (stream-fold-many f r streams)
167 (if (or-map stream-null? streams)
170 (apply f (let recur ((cars
171 (map stream-car streams)))
175 (recur (cdr cars))))))
176 (map stream-cdr streams))))
178 (define (stream-for-each f stream . rest)
179 (if (null? rest) ;fast path
180 (stream-for-each-one f stream)
181 (stream-for-each-many f (cons stream rest))))
183 (define (stream-for-each-one f stream)
184 (if (not (stream-null? stream))
186 (f (stream-car stream))
187 (stream-for-each-one f (stream-cdr stream)))))
189 (define (stream-for-each-many f streams)
190 (if (not (or-map stream-null? streams))
192 (apply f (map stream-car streams))
193 (stream-for-each-many f (map stream-cdr streams)))))
195 (define (stream-map f stream . rest)
196 "Returns a newly allocated stream, each element being the result of
197 invoking F with the corresponding elements of the STREAMs
199 (if (null? rest) ;fast path
200 (make-stream (lambda (s)
202 (cons (f (stream-car s)) (stream-cdr s))))
204 (make-stream (lambda (streams)
205 (or (or-map stream-null? streams)
206 (cons (apply f (map stream-car streams))
207 (map stream-cdr streams))))
208 (cons stream rest))))
210 (define (port->stream port read)
211 (make-stream (lambda (p)
217 ;;; streams.scm ends here