source: project/wiki/stream-ext @ 12730

Last change on this file since 12730 was 12730, checked in by azul, 12 years ago

More examples.

File size: 54.7 KB
Line 
1[[toc:]]
2[[tags:eggs streams]]
3
4== Introduction
5
6The stream-ext egg provides many convenient extensions to work with [[srfi:40]] streams.
7
8== Author
9
10This egg is made by [[http://azul.freaks-unidos.net/|Alejandro Forero Cuervo]] <azul@freaks-unidos.net>.
11
12<enscript highlight=scheme filename='stream-ext'>
13;; $Id: stream-ext.scm 5600 2006-05-19 20:01:00Z azul $
14;;
15;; This file is in the public domain and may be reproduced or copied without
16;; permission from its author.  Citation of the source is appreciated.
17;;
18;; Alejandro Forero Cuervo <azul@freaks-unidos.net>
19;;
20;; This file implements an egg for Chicken Scheme that contains useful
21;; extensions to work with streams as defined in srfi-40.
22;;
23;; Documentation is available in HTML format.
24;;
25;; Newer versions might be available at:
26;;
27;;    http://chicken.wiki.br/stream-ext
28</enscript>
29
30== Requires
31
32* [[srfi-40]]
33* [[format-modular]]
34
35<enscript highlight=scheme filename='stream-ext'>
36(require-extension srfi-40 srfi-1 format-modular)
37</enscript>
38
39== License
40
41The stream-ext egg for Chicken Scheme is in the public domain and may be reproduced or copied without
42permission from its author.  Citation of the source is appreciated.
43
44== Constructors
45
46=== stream-xcons
47
48<procedure>(stream-xcons stream object)</procedure>
49
50Creates a stream prepending {{object}} to {{stream}}.
51The name stands for "eXchanged CONS."
52
53Of utility only as a value to be conveniently passed to higher-order procedures.
54
55<examples testgroup="stream-xcons" filename="stream-ext">
56<example>
57<expr>(stream-xcons (stream 2 3) 1)</expr>
58<result>(stream 1 2 3)</result>
59<resultcmp>(cut stream= equal? <...>)</resultcmp>
60</example>
61<example>
62<expr>(stream-xcons (stream 2 3 4) 1)</expr>
63<result>(stream 1 2 3 4)</result>
64<resultcmp>(cut stream= = <...>)</resultcmp>
65</example>
66</examples>
67
68<enscript highlight=scheme filename='stream-ext'>
69(define (stream-xcons stream object) (stream-cons object stream))
70</enscript>
71
72=== stream-cons*
73
74<procedure>(stream-cons* [elt1 ...] tail)</procedure>
75
76Like {{stream}}, but the last argument
77provides the tail of the constructed stream, returning:
78
79<enscript highlight=scheme>(stream-cons elt1 (stream-cons elt2 (stream-cons ... eltn)))</enscript>
80
81<examples testgroup="stream-cons*" filename="stream-ext">
82<example>
83<expr>(stream-cons* 1 2 3 (stream 4))</expr>
84<result>(stream 1 2 3 4)</result>
85<resultcmp>(cut stream= = <...>)</resultcmp>
86</example>
87<example>
88<expr>(stream-cons* (stream 4))</expr>
89<result>(stream 4)</result>
90<resultcmp>(cut stream= = <...>)</resultcmp>
91</example>
92</examples>
93
94<enscript highlight=scheme filename='stream-ext'>
95(define (stream-cons* . elts)
96  (stream-delay
97   (if (null? (cdr elts))
98     (car elts)
99     (stream-cons (car elts) (apply stream-cons* (cdr elts))))))
100</enscript>
101</procedure>
102
103=== make-stream
104
105<procedure>(make-stream n [fill])</procedure>
106
107Returns an {{n}}-element stream, whose elements
108are all the value {{fill}}.
109If the {{fill}} argument is not given,
110the elements of the stream may be arbitrary values.
111
112<examples testgroup="make-stream" filename="stream-ext">
113<example>
114<expr>(make-stream 4 0)</expr>
115<result>(stream 0 0 0 0)</result>
116<resultcmp>(cut stream= = <...>)</resultcmp>
117</example>
118</examples>
119
120<enscript highlight=scheme filename='stream-ext'>
121(define (make-stream n . rest)
122  (let-optionals rest ((obj #f) (tail stream-null))
123    (stream-tabulate n (constantly obj) tail)))
124</enscript>
125
126=== stream-tabulate
127
128<procedure>(stream-tabulate n init-proc)</procedure>
129
130Returns an {{n}}-element list.
131Element {{i}} of the list, where 0 <= {{i}} < {{n}},
132is produced by {{(init-proc i)}}.
133
134<examples testgroup="make-stream" filename="stream-ext">
135<example>
136<expr>(stream-tabulate 4 (lambda (x) (* x x)))</expr>
137<result>(stream 0 4 9 16)</result>
138<resultcmp>(cut stream= = <...>)</resultcmp>
139</example>
140</examples>
141
142<enscript highlight=scheme filename='stream-ext'>
143(define (stream-tabulate n init-proc . rest)
144  (assert (number? n))
145  (assert (not (negative? n)))
146  (let-optionals rest ((tail stream-null))
147    (let loop ((i 0))
148      (stream-delay
149        (if (equal? i n)
150          tail
151          (stream-cons (init-proc i) (loop (+ i 1))))))))
152</enscript>
153
154=== stream-iota
155
156<procedure>(stream-iota a b)</procedure>
157
158Returns a list containing the elements:
159
160<enscript highlight=scheme>(start start+step ... start+(count-1)*step)</enscript>
161
162The {{start}} and {{step}} parameters default
163to {{0}} and {{1}}, respectively.
164This procedure takes its name from the APL primitive.
165
166<examples testgroup="stream-iota" filename="stream-ext">
167<example>
168<expr>(stream-iota 5)</expr>
169<result>(stream 0 1 2 3 4)</result>
170<resultcmp>(cut stream= = <...>)</resultcmp>
171</example>
172<example>
173<expr>(stream-iota 5 0 -0.1)</expr>
174<result>(stream 0 -0.1 -0.2 -0.3 -0.4)</result>
175<resultcmp>(cut stream= = <...>)</resultcmp>
176</example>
177</examples>
178
179<enscript highlight=scheme filename='stream-ext'>
180(define (stream-iota count . args)
181  (let loop ((i count)
182             (start (if (null? args) 0 (car args)))
183             (step (if (or (null? args) (null? (cdr args))) 1 (cadr args))))
184    (stream-delay
185      (if (zero? i)
186        stream-null
187        (stream-cons start (loop (- i 1) (+ start step) step))))))
188</enscript>
189
190=== make-infinite-stream
191
192TODO: Document
193
194<enscript highlight=scheme filename='stream-ext'>
195(define (make-infinite-stream proc start)
196  (stream-delay
197    (let ((next (proc start)))
198      (stream-cons next (make-infinite-stream proc next)))))
199</enscript>
200
201== Conversion
202
203=== stream->list
204
205<procedure>(stream->list str)</procedure>
206
207Returns a list with the elements in stream {{str}}.
208It is an error to pass an infinite stream.
209
210<enscript highlight=scheme filename='stream-ext'>
211(define (stream->list str)
212  (if (stream-null? str)
213    '()
214    (cons (stream-car str) (stream->list (stream-cdr str)))))
215</enscript>
216
217=== list->stream
218
219<procedure>(list->stream list)</procedure>
220
221Returns a stream with the elements in list {{list}}.
222The list might be circular (infinite), in which case the resulting
223stream will be infinite as well.
224
225<enscript highlight=scheme filename='stream-ext'>
226(define (list->stream list)
227  (stream-delay
228    (if (null? list)
229      stream-null
230      (stream-cons (car list) (list->stream (cdr list))))))
231</enscript>
232
233=== stream->string
234
235<procedure>(stream->string str)</procedure>
236
237Returns a string with its characters read from
238the stream {{str}}.
239It is an error if {{str}} does not end or if it
240has elements than are not characters.
241
242This function is the inverse of {{string->stream}}.
243
244<enscript highlight=scheme filename='stream-ext'>
245(define stream->string (compose list->string stream->list))
246</enscript>
247
248=== string->stream
249
250<procedure>(string->stream str [tail])</procedure>
251
252Returns a finite stream with the characters
253in the string {{str}}.  {{tail}}, which defaults to
254{{stream-null}}, is appended at the end.
255
256With {{tail}} set to {{stream-null}}, this function is the inverse of {{stream->string}}.
257
258<enscript highlight=scheme filename='stream-ext'>
259(define (string->stream str . rest)
260  (let-optionals rest ((tail stream-null))
261    (let loop ((i 0))
262      (stream-delay
263       (if (equal? i (string-length str))
264           tail
265           (stream-cons (string-ref str i) (loop (+ i 1))))))))
266</enscript>
267
268=== number->stream
269
270<procedure>(number->stream str)</procedure>
271
272...
273
274<enscript highlight=scheme filename='stream-ext'>
275(define number->stream (compose string->stream number->string))
276</enscript>
277
278=== stream->number
279
280<procedure>(stream->number str)</procedure>
281
282...
283
284<enscript highlight=scheme filename='stream-ext'>
285(define stream->number (compose string->number stream->string))
286</enscript>
287
288=== stream->vector
289
290<procedure>(stream->vector str)</procedure>
291
292...
293
294<enscript highlight=scheme filename='stream-ext'>
295(define stream->vector (compose list->vector stream->list))
296</enscript>
297
298=== vector->stream
299
300<procedure>(vector->stream str)</procedure>
301
302...
303
304<enscript highlight=scheme filename='stream-ext'>
305(define vector->stream (compose list->stream vector->list))
306</enscript>
307
308=== stream->symbol
309
310<procedure>(stream->symbol str)</procedure>
311
312...
313
314<enscript highlight=scheme filename='stream-ext'>
315(define stream->symbol (compose string->symbol stream->string))
316</enscript>
317
318=== symbol->stream
319
320<procedure>(symbol->stream str)</procedure>
321
322...
323
324<enscript highlight=scheme filename='stream-ext'>
325(define symbol->stream (compose string->stream symbol->string))
326</enscript>
327
328=== port->stream
329
330<procedure>(port->stream [in [reader [close-at-eof]]])</procedure>
331
332Returns a stream with the contents of the input port {{in}},
333which defaults to the current input port.
334
335{{reader}} is a procedure.  When called, it should read
336and return one element from the port passed as its only argument, advancing the
337read pointer (or return the eof object when no more elements
338are available in the port).  The default value is {{read-char}},
339which results in a stream of characters, but {{read}} and
340{{read-line}} can also be specified.
341
342{{close-at-eof}}, which defaults to {{close-input-port}}, will be
343called as soon as an end of file object is read from the port.
344A common idiom is to use:
345
346 (port->stream (open-input-file path))
347
348This will case the file to be closed as soon as the entire input is
349consumed.  However, the caller must be careful to actually read the entire
350stream before discarding it or file descriptors will be leaked.
351
352<enscript highlight=scheme filename='stream-ext'>
353(define (port->stream . rest)
354  (let-optionals rest ((in (current-input-port)) (reader read-char) (close-at-eof close-input-port))
355    (stream-delay
356      (let ((element (reader in)))
357        (cond
358          ((eof-object? element) (when close-at-eof (close-at-eof in)) stream-null)
359          (else (stream-cons element (port->stream in reader close-at-eof))))))))
360</enscript>
361
362=== iterator->stream
363
364<procedure>(iterator->stream proc)</procedure>
365
366Turns an iterator into a stream.  {{proc}} should be
367a procedure of two arguments.  The first is a one-argument
368procedure that collects objects (adds them to an enumeration)
369and the second is a procedure of no arguments that can be used
370to stop iteration prematurely.
371
372{{iterator->stream}} returns a stream.  The
373iterator {{proc}} is only allowed to run as objects
374are read from the stream (with {{stream-car}} or
375{{stream-cdr}}).
376
377Example:
378
379<enscript highlight=scheme>(define (list->stream alist)
380  (iterator->stream
381    (lambda (collect stop)
382      (for-each collect alist))))</enscript>
383
384<enscript highlight=scheme filename='stream-ext'>
385(define (iterator->stream proc)
386  (stream-delay
387    (call-with-current-continuation
388      (lambda (return)
389        (proc
390          (lambda (obj)
391            (call-with-current-continuation
392              (lambda (next)
393                (return
394                  (stream-cons obj
395                    (stream-delay
396                      (call-with-current-continuation
397                        (lambda (new)
398                          (set! return new)
399                          (next #t)))))))))
400          (lambda () (return stream-null)))
401        (return stream-null)))))
402</enscript>
403
404== Input and output
405
406=== with-output-to-stream
407
408<procedure>(with-output-to-stream proc)</procedure>
409
410Returns a stream of characters, which is built by calling
411{{proc}}, a procedure of no arguments, with its output
412port bound to a custom port.  As characters are read from the
413stream (by {{stream-car}} or {{stream-cdr}}),
414{{proc}} is allowed to execute until
415it writes as many characters as required.  For example,
416if the stream returned is immediately discarded, {{proc}}
417will not called at all.
418
419<examples testgroup="stream-xcons" filename="stream-ext">
420<example>
421<expr>(with-output-to-stream (lambda () (format #t "hi")))</expr>
422<result>(stream #\h #\i)</result>
423<resultcmp>(cut stream= equal? <...>)</resultcmp>
424</example>
425</examples>
426
427Remember that {{proc}} is only executed gradually,
428as the values from the stream are required.  As a consequence,
429certain problems could arise by uncareful use of non-reentrant
430functions.
431
432<enscript highlight=scheme filename='stream-ext'>
433(define (with-output-to-stream proc)
434  (iterator->stream
435    (lambda (write close)
436      (with-output-to-port
437        (make-output-port
438          (lambda (string)
439            (let loop ((i 0))
440              (when (< i (string-length string))
441                (write (string-ref string i))
442                (loop (+ i 1)))))
443          close)
444        proc))))
445</enscript>
446
447=== with-input-from-stream
448
449<procedure>(with-input-from-stream stream proc)</procedure>
450
451<enscript highlight=scheme filename='stream-ext'>
452(define (with-input-from-stream stream proc)
453  (with-input-from-port
454    (make-input-port
455      (lambda ()
456        (if (stream-null? stream)
457          #!eof
458          (let ((char (stream-car stream)))
459            (set! stream (stream-cdr stream))
460            char)))
461      (lambda ()
462        (not (stream-null? stream)))
463      (lambda ()
464        (set! stream stream-null))
465      (lambda ()
466        (stream-car stream)))
467    proc))
468</enscript>
469
470=== write-stream
471
472<procedure>(write-stream stream [port [writer]])</procedure>
473
474Write all the elements in the stream {{stream}} to the output port {{port}},
475which defaults to the current output port.
476If the stream is infinite, this function does not return.
477
478{{writer}} is the procedure used to write individual
479elements to the port.  It should receive the element to be written
480and the output port as its only arguments.  The default value is {{write-char}}
481but {{write}} and {{write-line}} can also be used (depending
482on the contents of {{stream}}).
483
484<enscript highlight=scheme filename='stream-ext'>
485(define (write-stream stream . rest)
486  (let-optionals rest ((port (current-output-port)) (writer write-char))
487    (let loop ((s stream))
488      (unless (stream-null? s)
489        (writer (stream-car s) port)
490        (loop (stream-cdr s))))))
491</enscript>
492
493== Predicates
494
495=== stream=
496
497<procedure>(stream= elt= str1 ...)</procedure>
498
499Determines stream equality, given an element-equality procedure.
500Stream {{A}} equals stream {{B}} if they are of the
501same length, and their corresponding elements are equal, as determined
502by {{elt=}}.
503If the element-comparison procedure's first argument is from stri,
504then its second argument is from stri+1, i.e. it is always called
505as {{(elt= a b)}} for {{a}} an element of stream {{A}},
506and {{b}} an element of stream {{B}}.
507
508In the n-ary case, every {{stri}} is compared to {{stri+1}}
509(as opposed, for example, to comparing {{str1}} to every {{stri}},
510for {{i}} > 1).
511If there are no list arguments at all, {{stream=}} simply returns true.
512
513The dynamic order in which the {{elt=}} procedure is applied to pairs of
514elements is not specified. For example, if {{stream=}} is applied to three lists,
515{{A}}, {{B}},
516and {{C}}, it may first completely compare
517{{A}} to {{B}},
518then compare {{B}} to {{C}}, or it may
519compare the first elements of {{A}} and {{B}},
520then the first elements of {{B}} and {{C}},
521then the second elements of {{A}} and {{B}}, and so forth.
522
523The equality procedure must be consistent with {{eq?}}.
524That is, it must be the case that:
525
526<enscript highlight=scheme>(eq? x y) => (elt= x y)</enscript>
527
528This implies that two lists which are {{eq?}} are always {{stream=}}
529as well; implementations may exploit this fact to "short-cut" the element-by-element comparisons.
530
531<enscript highlight=scheme>(stream= eq?)
532=> #t       ; Trivial cases
533(stream= eq? (stream 0 1 2))
534=> #t</enscript>
535
536<enscript highlight=scheme filename='stream-ext'>
537(define (stream= elt= . strs)
538  (or (every stream-null? strs)
539      (and (not (any stream-null? strs))
540           (let loop ((es (map stream-car strs)))
541             (or (null? (cdr es))
542                 (and (elt= (car es) (cadr es)) (loop (cdr es)))))
543           (apply stream= elt= (map stream-cdr strs)))))
544</enscript>
545
546=== stream-prefix=
547
548<procedure>(stream-prefix= str prefix [=])</procedure>
549
550Evaluates whether the elements at the beginning of stream
551{{str}} are equal to the elements in the list
552{{prefix}}.
553
554{{eq}} is the function used to compare the individual elements.
555The default is {{equal?}}.
556
557If the prefix of the stream matches {{prefix}}, the
558function returns the contents of {{stream}} following
559it.  False is returned otherwise.
560
561<enscript highlight=scheme>(stream-prefix= (stream 1 2 3 4) '(1 2))
562=> #<stream (3 4)>
563(stream-prefix= (stream 1 2 3 4) '(1 3))
564=> #f</enscript>
565
566<enscript highlight=scheme filename='stream-ext'>
567(define (stream-prefix= str prefix . rest)
568  (if (null? prefix)
569    str
570    (and (not (stream-null? str))
571         ((if (null? rest) equal? (car rest)) (stream-car str) (car prefix))
572         (apply stream-prefix= (stream-cdr str) (cdr prefix) rest))))
573</enscript>
574
575=== stream>, stream<
576
577...
578
579<enscript highlight=scheme filename='stream-ext'>
580(define (stream< elt< . strs)
581  (or (null? strs)
582      (null? (cdr strs))
583      (and
584        (let loop ((a (car strs)) (b (cadr strs)))
585          (or (elt< (stream-car a) (stream-car b))
586              (and (not (elt< (stream-car b) (stream-car a)))
587                   (loop (stream-cdr a) (stream-cdr b)))))
588        (apply stream< elt (cdr strs)))))
589
590(define (stream> elt< . strs) (apply stream< (complement elt<) strs))
591</enscript>
592
593== Selectors
594
595=== stream-caar ... stream-cddddr
596
597<procedure>(stream-caar stream)</procedure>
598<procedure>(stream-cadr stream)</procedure>
599<procedure>(stream-cdar stream)</procedure>
600<procedure>(stream-cddr stream)</procedure>
601
602<procedure>(stream-caaar stream)</procedure>
603<procedure>(stream-caadr stream)</procedure>
604<procedure>(stream-cadar stream)</procedure>
605<procedure>(stream-caddr stream)</procedure>
606<procedure>(stream-cdaar stream)</procedure>
607<procedure>(stream-cdadr stream)</procedure>
608<procedure>(stream-cddar stream)</procedure>
609<procedure>(stream-cdddr stream)</procedure>
610
611<procedure>(stream-caaaar stream)</procedure>
612<procedure>(stream-caaadr stream)</procedure>
613<procedure>(stream-caadar stream)</procedure>
614<procedure>(stream-caaddr stream)</procedure>
615<procedure>(stream-cadaar stream)</procedure>
616<procedure>(stream-cadadr stream)</procedure>
617<procedure>(stream-caddar stream)</procedure>
618<procedure>(stream-cadddr stream)</procedure>
619<procedure>(stream-cdaaar stream)</procedure>
620<procedure>(stream-cdaadr stream)</procedure>
621<procedure>(stream-cdadar stream)</procedure>
622<procedure>(stream-cdaddr stream)</procedure>
623<procedure>(stream-cddaar stream)</procedure>
624<procedure>(stream-cddadr stream)</procedure>
625<procedure>(stream-cdddar stream)</procedure>
626<procedure>(stream-cddddr stream)</procedure>
627
628These procedures are compositions of
629{{stream-car}} and {{stream-cdr}},
630where for example {{stream-caddr}} could be defined by:
631
632<enscript highlight=scheme>(define (stream-caddr x) (stream-car (stream-cdr (stream-cdr x))))</enscript>
633
634Arbitrary compositions, up to four deep, are provided.
635There are twenty-eight of these procedures in all.
636
637<enscript highlight=scheme filename='stream-ext'>
638(define stream-caar   (compose stream-car stream-car))
639(define stream-cadr   (compose stream-car stream-cdr))
640(define stream-cdar   (compose stream-cdr stream-car))
641(define stream-cddr   (compose stream-cdr stream-cdr))
642
643(define stream-caaar  (compose stream-caar stream-car))
644(define stream-caadr  (compose stream-caar stream-cdr))
645(define stream-cadar  (compose stream-cadr stream-car))
646(define stream-caddr  (compose stream-cadr stream-cdr))
647(define stream-cdaar  (compose stream-cdar stream-car))
648(define stream-cdadr  (compose stream-cdar stream-cdr))
649(define stream-cddar  (compose stream-cddr stream-car))
650(define stream-cdddr  (compose stream-cddr stream-cdr))
651
652(define stream-caaaar (compose stream-caaar stream-car))
653(define stream-caaadr (compose stream-caaar stream-cdr))
654(define stream-caadar (compose stream-caadr stream-car))
655(define stream-caaddr (compose stream-caadr stream-cdr))
656(define stream-cadaar (compose stream-cadar stream-car))
657(define stream-cadadr (compose stream-cadar stream-cdr))
658(define stream-caddar (compose stream-caddr stream-car))
659(define stream-cadddr (compose stream-caddr stream-cdr))
660(define stream-cdaaar (compose stream-cdaar stream-car))
661(define stream-cdaadr (compose stream-cdaar stream-cdr))
662(define stream-cdadar (compose stream-cdadr stream-car))
663(define stream-cdaddr (compose stream-cdadr stream-cdr))
664(define stream-cddaar (compose stream-cddar stream-car))
665(define stream-cddadr (compose stream-cddar stream-cdr))
666(define stream-cdddar (compose stream-cdddr stream-car))
667(define stream-cddddr (compose stream-cdddr stream-cdr))
668</enscript>
669
670=== stream-ref
671
672<procedure>(stream-ref str pos)</procedure>
673
674Returns the element in the stream {{str}} at the
675position {{pos}}.  This is the same as the stream-car
676of {{(stream-drop str pos)}}. It is an error if
677{{str}} has {{pos}} or fewer elements.
678
679<enscript highlight=scheme>(stream-ref (stream 0 1 2 3 4 5) 3)
680=> 3</enscript>
681
682<enscript highlight=scheme filename='stream-ext'>
683(define (stream-ref str pos)
684  (if (zero? pos)
685      (stream-car str)
686      (stream-ref (stream-cdr str) (- pos 1))))
687</enscript>
688
689=== stream-first ... stream-tenth
690
691<procedure>(stream-first str)</procedure>
692<procedure>(stream-second str)</procedure>
693<procedure>(stream-third str)</procedure>
694<procedure>(stream-fourth str)</procedure>
695<procedure>(stream-fifth str)</procedure>
696<procedure>(stream-sixth str)</procedure>
697<procedure>(stream-seventh str)</procedure>
698<procedure>(stream-sixth str)</procedure>
699<procedure>(stream-eighth str)</procedure>
700<procedure>(stream-tenth str)</procedure>
701
702Synonyms for {{(stream-car str)}},
703{{(stream-cadr str)}}, {{(stream-caddr str)}}, ...
704
705<enscript highlight=scheme>(stream-third (stream 0 1 2 3 4))
706=> 2</enscript>
707
708<enscript highlight=scheme filename='stream-ext'>
709(define stream-first   stream-car)
710(define stream-second  stream-cadr)
711(define stream-third   stream-caddr)
712(define stream-fourth  stream-cadddr)
713(define stream-fifth   (compose stream-car    stream-cddddr))
714(define stream-sixth   (compose stream-cadr   stream-cddddr))
715(define stream-seventh (compose stream-caddr  stream-cddddr))
716(define stream-eighth  (compose stream-cadddr stream-cddddr))
717(define stream-ninth   (compose stream-car    stream-cddddr stream-cddddr))
718(define stream-tenth   (compose stream-cadr   stream-cddddr stream-cddddr))
719</enscript>
720
721=== stream-take, stream-take-safe
722
723<procedure>(stream-take str count)</procedure>
724<procedure>(stream-take-safe str count)</procedure>
725
726Returns a stream with the first {{count}} elements
727in stream {{str}}.  For {{stream-take}}, it is an error if {{str}}
728has fewer than {{count}} elements; for {{stream-take-safe}}, {{str}}
729will be returned.
730
731<enscript highlight=scheme>(stream-take (stream 1 2 3 4 5) 2)
732=> #<stream (1 2)></enscript>
733
734<enscript highlight=scheme filename='stream-ext'>
735(define (stream-take stream count)
736  (stream-delay
737   (if (zero? count)
738       stream-null
739       (stream-cons (stream-car stream)
740                    (stream-take (stream-cdr stream) (- count 1))))))
741
742(define (stream-take-safe stream count)
743  (stream-delay
744    (if (or (zero? count) (stream-null? stream))
745      stream-null
746      (stream-cons (stream-car stream)
747                   (stream-take-safe (stream-cdr stream) (- count 1))))))
748</enscript>
749
750=== stream-drop, stream-drop-safe
751
752<procedure>(stream-drop str count)</procedure>
753<procedure>(stream-drop-safe str count)</procedure>
754
755Returns the sub-stream of {{str}} obtained by omitting
756the first {{count}} elements.  For {{stream-drop}}, it is an error if {str}} has
757fewer than {{count}} elements; for {{stream-drop-safe}}, the empty stream
758will be returned.
759
760<enscript highlight=scheme>(stream-drop (stream 0 1 2 3 4 5) 3)
761=> #<stream (3 4 5)></enscript>
762
763<enscript highlight=scheme filename='stream-ext'>
764(define (stream-drop str count)
765  (stream-delay
766   (if (zero? count)
767       str
768       (stream-drop (stream-cdr str) (- count 1)))))
769
770(define (stream-drop-safe str count)
771  (stream-delay
772    (if (or (zero? count) (stream-null? str))
773      str
774      (stream-drop-safe (stream-cdr str) (- count 1)))))
775
776
777
778</enscript>
779
780=== stream-intersperse
781
782<procedure>(stream-intersperse stream element)</procedure>
783
784Returns a new stream with the elements in the stream {{stream}}
785but placing {{element}} between each.
786
787<enscript highlight=scheme>(stream-intersperse (stream 0 1 2 3) #f)
788=> #<stream (0 #f 1 #f 2 #f 3)>
789(stream-intersperse (stream 0) 1)
790=> #<stream (0)></enscript>
791
792<enscript highlight=scheme filename='stream-ext'>
793(define (stream-intersperse stream element . rest)
794  (let-optionals rest ((tail stream-null))
795    (stream-delay
796      (if (stream-null? stream)
797        tail
798        (stream-cons (stream-car stream)
799          (let loop ((rest (stream-cdr stream)))
800            (if (stream-null? rest)
801              tail
802              (stream-cons element (stream-cons (stream-car rest) (loop (stream-cdr rest)))))))))))
803</enscript>
804
805=== stream-split
806
807<procedure>(stream-split str pred)</procedure>
808
809Splits the stream {{str}} into multiple streams, removing
810the elements satisfying predicate {{pred}}.
811This is similar to what {{string-split}} does
812but operates on streams (rather than strings) and returns the result
813as a stream of streams (rather than a list of strings).
814
815Example:
816
817<enscript highlight=scheme>(stream-split (stream 1 2 3 5 7 8 9 10) even?)
818=> #<stream (#<stream (1)> #<stream (3 5 7)> #<stream (9)>)></enscript>
819
820<enscript highlight=scheme filename='stream-ext'>
821(define (stream-split in p?)
822  (let loop ((current '()) (s in))
823    (stream-delay
824      (cond
825        ((stream-null? s)
826           (if (null? current)
827             stream-null
828             (stream-cons (list->stream (reverse current)) stream-null)))
829        ((p? (stream-car s))
830           (stream-cons (list->stream (reverse current)) (loop '() (stream-cdr s))))
831        (else (loop (cons (stream-car s) current) (stream-cdr s)))))))
832</enscript>
833
834=== stream-last
835
836<procedure>(stream-last str)</procedure>
837
838Returns the last element of the non-empty finite stream {{str}}.
839It is an error to pass an empty stream.
840
841<enscript highlight=scheme>(stream-last (stream 'a 'b 'c))
842=> c</enscript>
843
844{{stream-last}} could be defined as:
845
846<enscript highlight=scheme>(define (stream-last stream)
847  (stream-car (stream-last-n stream 1)))</enscript>
848
849<enscript highlight=scheme filename='stream-ext'>
850(define (stream-last str)
851  (if (stream-null? (stream-cdr str))
852    (stream-car str)
853    (stream-last (stream-cdr str))))
854</enscript>
855
856=== stream-last-n
857
858<rocedure>(stream-last-n stream count)</procedure>
859
860Returns a stream with the last {{count}}
861elements of the finite stream {{str}}.  If fewer
862than {{count}} elements are available in {{stream}},
863{{stream}} itself is returned.
864
865<enscript highlight=scheme>(stream-null? (stream-last-n (stream #\a #\b #\c #\d) 0))
866=> #t
867(stream-last-n (stream #\a #\b #\c #\d) 1)
868=> #<stream (#\d)>
869(stream-last-n (stream #\a #\b #\c #\d) 3)
870=> #<stream (#\b #\c #\d)>
871(stream-last-n (stream #\a #\b #\c #\d) 20)
872=> #<stream (#\a #\b #\c #\d)></enscript>
873
874<enscript highlight=scheme filename='stream-ext'>
875(define (stream-last-n str count)
876  (stream-delay
877    (let ((l (list #f)))
878      (set-cdr! l l)
879      (let loop ((s str) (l l) (i 0))
880        (cond
881          ((stream-null? s)
882           (if (< i count)
883             str
884             (stream-take (list->stream (cdr l)) i)))
885          ((equal? i count)
886             (set-car! l (stream-car s))
887             (loop (stream-cdr s) (cdr l) i))
888          (else
889            (set-car! l (stream-car s))
890            (set-cdr! l (cons i (cdr l)))
891            (loop (stream-cdr s) (cdr l) (+ i 1))))))))
892</enscript>
893
894=== stream-butlast
895
896<procedure>(stream-butlast stream)</procedure>
897
898Returns a stream with all the elements in the
899non-empty stream {{str}} except the last.
900The order of the elements is respected.
901
902<enscript highlight=scheme>(stream-butlast (stream #\a #\b #\c))
903=> #<stream (#\a #\b)></enscript>
904
905{{stream-butlast}} can be defined as:
906
907<enscript highlight=scheme filename='stream-ext'>
908(define (stream-butlast str)
909  (stream-butlast-n str 1))
910</enscript>
911
912=== stream-butlast-n
913
914<procedure>(stream-butlast-n stream count)</procedure>
915
916Returns a stream with all the elements in the
917stream {{stream}} except the last
918{{count}}.  The order of the elements is
919respected.  It is an error if {{stream}}
920has fewer than {{count}} elements.
921
922<enscript highlight=scheme>(stream-butlast-n (stream #\a #\b #\c) 2)
923=> #<stream (#\a)>
924(stream-null? (stream-butlast-n (stream #\a #\b #\c) 3))
925=> #t</enscript>
926
927<enscript highlight=scheme filename='stream-ext'>
928(define (stream-butlast-n str count)
929  (stream-delay
930    (let loop ((head str) (tail (stream-drop str count)))
931      (if (stream-null? tail)
932        stream-null
933        (stream-cons (stream-car head) (loop (stream-cdr head) (stream-cdr tail)))))))
934</enscript>
935
936== Miscellaneous: length, append, concatenate, reverse, zip & count
937
938=== stream-length
939
940<procedure>(stream-length str)</procedure>
941
942Returns the length of the argument stream (a non-negative integer n such that
943stream-cdr applied n times to the stream produces the null stream).
944
945This function does not return when {{str}} is an
946infinite streams.
947
948Returns the length of the stream {{str}}.
949This call does not return if {{str}} is an
950infinite stream.
951
952<enscript highlight=scheme>(stream-length (stream 0 1 2 3))
953=> 4</enscript>
954
955<enscript highlight=scheme filename='stream-ext'>
956(define (stream-length str)
957  (let loop ((i 0) (s str))
958    (if (stream-null? s)
959        i
960        (loop (+ i 1) (stream-cdr s)))))
961</enscript>
962
963=== stream-length>=
964
965<procedure>(stream-length>= str len)</procedure>
966
967Returns {{#t}} if the length of the stream {{str}}
968is greater or equal than {{len}}, {{#f}} otherwise.
969
970For finite streams, this is equivalent, albeit faster (specially when
971{{len}} is significantly smaller than the length of {{str}}), to:
972
973<enscript highlight=scheme>(>= (stream-length str) len)</enscript>
974
975However, for infinite streams it is equivalent to {{#t}}
976(whereas the above code would never terminate).
977
978<enscript highlight=scheme filename='stream-ext'>
979(define (stream-length>= str len)
980  (or (zero? len)
981      (and (not (stream-null? str))
982           (stream-length>= (stream-cdr str) (- len 1)))))
983</enscript>
984
985=== stream-append
986
987<procedure>(stream-append str1 str2 ...)</procedure>
988
989{{stream-append}} returns a stream consisting of the elements of str1
990followed by the elements of the other stream parameters.
991
992<enscript highlight=scheme>(stream-append (stream 1) (stream 2))
993=> #<stream (1 2)>
994(stream-append (stream 1) (stream 2 3 4))
995=> #<stream (1 2 3 4)>
996(stream-append (stream 'a '(b)) (stream '(c)))
997=> #<stream (a (b) (c))></enscript>
998
999<enscript highlight=scheme filename='stream-ext'>
1000(define (stream-append . strs)
1001  (stream-delay
1002    (cond
1003      ((null? strs) stream-null)
1004      ((null? (cdr strs)) (car strs))
1005      (else
1006        (let loop ((c (car strs)) (rest (cdr strs)))
1007          (stream-delay
1008            (if (stream-null? c)
1009              (apply stream-append rest)
1010              (stream-cons (stream-car c) (loop (stream-cdr c) rest)))))))))
1011</enscript>
1012
1013=== stream-concatenate
1014
1015<procedure>(stream-concatenate str)</procedure>
1016
1017...
1018
1019<enscript highlight=scheme filename='stream-ext'>
1020(define (stream-concatenate strs)
1021  (stream-delay
1022    (if (stream-null? strs)
1023      stream-null
1024      (stream-append (stream-car strs) (stream-concatenate (stream-cdr strs))))))
1025</enscript>
1026
1027=== stream-reverse
1028
1029<procedure>(stream-reverse str)</procedure>
1030
1031{{stream-reverse}}
1032returns a stream consisting of the elements of
1033the stream {{str}} in reverse order.
1034
1035This procedure does not return if {{str}} is an infinite
1036stream.
1037
1038<enscript highlight=scheme>(stream-reverse (stream 1 2 3))
1039=> #<stream (3 2 1)>
1040(stream-reverse (stream 'a '(b c) 'd '(e (f))))
1041=> #<stream ((e (f)) d (b c) a)></enscript>
1042
1043<enscript highlight=scheme filename='stream-ext'>
1044(define (stream-reverse str . args)
1045  (stream-delay
1046    (let-optionals args ((tail stream-null))
1047      (let loop ((head str) (tail tail))
1048        (if (stream-null? head)
1049          tail
1050          (loop (stream-cdr head) (stream-cons (stream-car head) tail)))))))
1051</enscript>
1052
1053=== stream-count
1054
1055<procedure>(stream-count pred str1 str2 ...)</procedure>
1056
1057{{pred}} is a procedure taking as many arguments as there are streams and
1058returning a single value. It is applied element-wise to the elements of the
1059streams, and a count is tallied of the number of elements that produce a true
1060value. This count is returned. count is "iterative" in that it is guaranteed to
1061apply {{pred}} to the stream elements in a left-to-right order. The counting stops
1062when the shortest list expires.
1063
1064If all the streams are infinite, this procedure does not return.
1065
1066<enscript highlight=scheme>(stream-count even? (stream 3 1 4 1 5 9 2 5 6))
1067=> 3
1068(stream-count < (stream 1 2 4 8) (stream 2 4 6 8 10 12 14 16))
1069=> 3
1070(stream-count < (stream 3 1 4 1) (make-stream #t 2))
1071=> 2</enscript>
1072
1073<enscript highlight=scheme filename='stream-ext'>
1074(define (stream-count pred . strs)
1075  (apply
1076    stream-fold
1077    (lambda args
1078      (+ (last args)
1079         (if (apply pred (butlast args)) 1 0)))
1080    0
1081    strs)
1082</enscript>
1083
1084== Fold
1085
1086=== stream-fold
1087
1088...
1089
1090<enscript highlight=scheme filename='stream-ext'>
1091(define (stream-fold func nil . strs)
1092  (if (any stream-null? str)
1093    nil
1094    (apply
1095      stream-fold
1096      func
1097      (apply (cut func <...> nil) (map stream-car strs))
1098      (map stream-cdr strs))))
1099</enscript>
1100
1101=== stream-fold-right
1102
1103...
1104
1105<enscript highlight=scheme filename='stream-ext'>
1106(define (stream-fold-right func nil str)
1107  (if (stream-null? str)
1108    nil
1109    (func (stream-car str) (stream-fold-right func nil (stream-cdr str)))))
1110</enscript>
1111
1112=== stream-fold-right-delay
1113
1114...
1115
1116Similar to {{stream-fold-right}}, but useful when the result of the folding
1117procedure is a stream; in this case, the evaluation of the fold is done in a
1118lazy manner.
1119
1120<enscript highlight=scheme filename='stream-ext'>
1121(define (stream-fold-right-delay func nil str)
1122  (stream-delay
1123    (if (stream-null? str)
1124      nil
1125      (func (stream-car str) (stream-fold-right-delay func nil (stream-cdr str))))))
1126</enscript>
1127
1128== Filtering & Partitioning
1129
1130=== stream-partition
1131
1132<procedure>(stream-partition pred str)</procedure>
1133
1134Partitions the elements of stream {{str}} with predicate
1135{{pred}}, and returns two values: the stream of in-elements
1136and the stream of out-elements.
1137The stream is not disordered -- elements occur in the result streams
1138in the same order as they occur in the argument stream.
1139
1140The dynamic order in which the various applications of {{pred}}
1141depends on the evaluation of the streams.  {{pred}} might be evaluated
1142twice for each element in the argument stream.
1143
1144<enscript highlight=scheme>(stream-partition symbol? (stream 'one 2 3 'four 'five 6))
1145=>
1146   #<stream (one four five)>
1147   #<stream (2 3 6)></enscript>
1148
1149<enscript highlight=scheme filename='stream-ext'>
1150(define (stream-partition pred str)
1151  (values (stream-filter pred str)
1152          (stream-remove pred str)))
1153</enscript>
1154
1155=== stream-remove
1156
1157<procedure>(stream-remove pred str)</procedure>
1158
1159Returns a stream with all the elements in the stream {{str}}
1160except those that satisfy predicate pred:
1161
1162<enscript highlight=scheme>(lambda (pred str) (stream-filter (lambda (x) (not (pred x))) str))</enscript>
1163
1164The stream is not disordered -- elements that appear in the result list
1165occur in the same order as they occur in the argument list.
1166
1167<enscript highlight=scheme>(stream-remove even? (stream 0 7 8 8 43 -4))
1168=> #<stream (7 43)></enscript>
1169
1170<enscript highlight=scheme filename='stream-ext'>
1171(define (stream-remove pred str)
1172  (stream-filter (complement pred) str))
1173</enscript>
1174
1175== Searching
1176
1177=== stream-find
1178
1179<procedure>(stream-find pred str)</procedure>
1180
1181Return the first element of the stream {{str}}
1182that satisfies predicate {{pred}};
1183false if no element does.
1184
1185<enscript highlight=scheme>(stream-find even? (stream 3 1 4 1 5 9))
1186=> 4</enscript>
1187
1188Note that {{stream-find}} has an ambiguity in
1189its lookup semantics -- if find returns {{#f}},
1190you cannot tell (in general) if it found a {{#f}} element that
1191satisfied {{pred}}, or if it did not find any element at all.
1192In many situations, this ambiguity cannot arise -- either the list
1193being searched is known not to contain any {{#f}} elements, or the
1194list is guaranteed to have an element satisfying {{pred}}.
1195However, in cases where this ambiguity can arise, you should use
1196{{stream-find-tail}} instead of {{stream-find}}
1197-- {{stream-find-tail}} has no such ambiguity:
1198
1199<enscript highlight=scheme>(cond ((stream-find-tail pred lis) => (lambda (pair) ...)) ; Handle (CAR PAIR)
1200      (else ...)) ; Search failed.</enscript>
1201
1202<enscript highlight=scheme filename='stream-ext'>
1203(define (stream-find pred str)
1204  (let ((result (stream-find-tail pred str)))
1205    (and result (stream-car result))))
1206</enscript>
1207
1208=== stream-find-tail
1209
1210<procedure>(stream-find-tail pred str)</procedure>
1211
1212Returns the first stream-pair of {{str}}
1213whose car satisfies predicate {{pred}}.
1214If no pair does, returns false.
1215
1216<enscript highlight=scheme>(stream-find-tail even? (stream 3 1 37 -8 -5 0 0))
1217=> #<stream (-8 -5 0 0)>
1218(stream-find-tail even? (stream 3 1 37 -5))
1219=> #f</enscript>
1220
1221{{stream-find-tail}} can be viewed as a general-predicate
1222variant of the {{stream-member}} function.  {{stream-member}}
1223can be defined as a call to stream-find-tail:
1224
1225<enscript highlight=scheme>;; (stream-member x str):
1226(stream-find-tail (lambda (elt) (equal? x elt)) str)</enscript>
1227
1228Find-tail is essentially stream-drop-while, where the sense of the
1229predicate is inverted: Find-tail searches until it finds an element
1230satisfying the predicate; drop-while searches until it finds an
1231element that doesn't satisfy the predicate.
1232
1233<enscript highlight=scheme filename='stream-ext'>
1234(define (stream-find-tail pred str)
1235  (and (not (stream-null? str))
1236       (if (pred (stream-car str))
1237           str
1238           (stream-find-tail pred (stream-cdr str)))))
1239</enscript>
1240
1241=== stream-take-while
1242
1243<procedure>(stream-take-while pred str)</procedure>
1244
1245Returns the longest initial prefix of stream {{str}}
1246whose elements all satisfy the predicate {{pred}}.
1247
1248<enscript highlight=scheme>(stream-take-while even? (stream 2 18 3 10 22 9))
1249=> #<stream (2 18)></enscript>
1250
1251<enscript highlight=scheme filename='stream-ext'>
1252(define (stream-take-while pred str)
1253  (stream-delay
1254   (if (or (stream-null? str) (not (pred (stream-car str))))
1255       stream-null
1256       (stream-cons (stream-car str)
1257         (stream-take-while pred (stream-cdr str))))))
1258</enscript>
1259
1260=== stream-drop-while
1261
1262<procedure>(stream-drop-while pred str)</procedure>
1263
1264Drops the longest initial prefix of stream {{str}} whose
1265elements all satisfy the predicate {{pred}} and returns
1266the rest of the stream.
1267
1268<enscript highlight=scheme>(stream-drop-while even? (stream 2 18 3 10 22 9))
1269=> #<stream (3 10 22 9)></enscript>
1270
1271<enscript highlight=scheme filename='stream-ext'>
1272(define (stream-drop-while pred str)
1273  (stream-delay
1274   (if (or (stream-null? str) (not (pred (stream-car str))))
1275       str
1276       (stream-drop-while pred (stream-cdr str)))))
1277</enscript>
1278
1279=== stream-span, stream-break
1280
1281<procedure>(stream-span pred str)</procedure>
1282<procedure>(stream-break pred str)</procedure>
1283
1284{{stream-span}} splits the stream {{str}} into the longest
1285initial prefix whose elements all satisfy predicate {{pred}}, and the
1286remaining tail.  {{stream-break}} inverts the sense of the predicate:
1287the tail commences with the first element of the input list that satisfies the
1288predicate.
1289
1290In other words: {{stream-span}} finds the intial span of elements
1291satisfying {{pred}}, and {{stream-break}} breaks the list at
1292the first element not satisfying {{pred}}.
1293
1294stream-span is equivalent to:
1295
1296<enscript highlight=scheme>(values (stream-take-while pred str) (stream-drop-while pred str))</enscript>
1297
1298Examples:
1299
1300<enscript highlight=scheme>(stream-span even? (stream 2 18 3 10 22 9))
1301=>
1302  #<stream (2 18)>
1303  #<stream (3 10 22 9)>
1304(stream-break even? (stream 3 1 4 1 5 9))
1305=>
1306  #<stream (3 1)>
1307  #<stream (4 1 5 9)></enscript>
1308
1309<enscript highlight=scheme filename='stream-ext'>
1310(define (stream-span pred str)
1311  (values (stream-take-while pred str) (stream-drop-while pred str)))
1312
1313(define (stream-break pred str)
1314  (stream-span (complement pred) str))
1315</enscript>
1316
1317=== stream-any
1318
1319<procedure>(stream-any pred str1 str2 ...)</procedure>
1320
1321Applies the predicate {{pred}}
1322across the streams {{str1 ... strn}},
1323returning true if the predicate returns true on any application.
1324
1325If there are {{n}} stream arguments
1326{{str1 ... strn}}, then {{pred}}
1327must be a procedure taking {{n}} arguments
1328and returning a boolean result.
1329
1330{{stream-any}} applies {{pred}} to the first
1331elements of the {{stri}} parameters.
1332If this application returns a true value, {{stream-any}}
1333immediately returns that value. Otherwise, it iterates, applying
1334{{pred}} to the second elements of the {{stri}}
1335parameters, then the third, and so forth. The iteration stops when
1336a true value is produced or one of the streams runs out of values;
1337in the latter case, {{stream-any}} returns #f.
1338
1339Just like with {{any}} (see SRFI-1), it would be desirable
1340to make the last call to {{pred}} a tail call.  However,
1341this would force {{stream-any}} to evaluate streams in
1342advance.  For this reason, the last call to {{pred}} is
1343not a tail call.
1344
1345Note the difference between {{stream-find}}
1346and {{stream-any}} -- {{stream-find}} returns the element that
1347satisfied the predicate; {{stream-any}} returns the true value that the
1348predicate produced.
1349
1350Like {{stream-every}}, {{stream-any}}'s name
1351does not end with a question mark -- this is to indicate that it
1352does not return a simple boolean ({{#t}} or {{#f}}),
1353but a general value.
1354
1355<enscript highlight=scheme>(stream-any integer? (stream 'a 3 'b 2.7))
1356=> #t
1357(stream-any integer? (stream 'a 3.1 'b 2.7))
1358=> #f
1359(stream-any < (stream 3 1 4 1 5) (stream 2 7 1 8 2))
1360=> #t</enscript>
1361
1362<enscript highlight=scheme filename='stream-ext'>
1363(define (stream-any pred . strs)
1364  (and (not (find stream-null? strs))
1365       (or (apply pred (map stream-car strs))
1366           (apply stream-any pred (map stream-cdr strs)))))
1367</enscript>
1368
1369=== stream-every
1370
1371<procedure>(stream-every pred str1 str2 ...)</procedure>
1372
1373Applies the predicate across the streams,
1374returning true if the predicate returns true on every application.
1375
1376If there are {{n}} stream arguments
1377{{str1 ... strn}}, then {{pred}} must be a procedure
1378taking {{n}} arguments and returning a boolean result.
1379
1380{{stream-every}} applies {{pred}} to the first
1381elements of the {{stri}} parameters. If this application
1382returns false, {{stream-every}} immediately returns false.
1383Otherwise, it iterates, applying {{pred}} to the second
1384elements of the {{stri}} parameters, then the third, and
1385so forth. The iteration stops when a false value is produced or one
1386of the lists runs out of values. In the latter case, every returns
1387the true value produced by its final application of pred.
1388
1389Just like with {{every}} (see SRFI-1), it would be desirable
1390to make the last call to {{pred}} a tail call.  However,
1391this would force {{stream-every}} to evaluate streams in
1392advance.  For this reason, the last call to {{pred}} is
1393not a tail call.
1394
1395If one of the {{stri}}
1396has no elements, every simply returns #t.
1397
1398Like {{stream-any}}, {{stream-every}}'s
1399name does not end with a question mark -- this is to indicate
1400that it does not return a simple boolean (#t or #f), but a general value.
1401
1402<enscript highlight=scheme filename='stream-ext'>
1403(define (stream-every pred . strs)
1404  (let loop ((strs strs))
1405    (or (find stream-null? strs)
1406        (and (apply pred (map stream-car strs))
1407             (loop (map stream-cdr strs))))))
1408</enscript>
1409
1410=== stream-index
1411
1412<procedure>(stream-index pred str1 str2 ...)</procedure>
1413
1414Return the index of the leftmost elements in the
1415streams that satisfies predicate {{pred}}.
1416
1417If there are {{n}} list arguments {{str1 ... strn}},
1418then {{pred}} must be a function taking {{n}} arguments
1419and returning a boolean result.
1420
1421stream-index applies {{pred}} to the first elements of the
1422{{stri}} parameters. If this application returns true,
1423{{stream-index}} immediately returns zero. Otherwise, it
1424iterates, applying {{pred}} to the second elements of the
1425{{stri}} parameters, then the third, and so forth. When it
1426finds a tuple of list elements that cause {{pred}} to
1427return true, it stops and returns the zero-based index of that
1428position in the lists.
1429
1430The iteration stops when one of the lists runs out of values;
1431in this case, {{stream-index}} returns {{#f}}.
1432
1433<enscript highlight=scheme>(stream-index even? (stream 3 1 4 1 5 9))
1434=> 2
1435(stream-index < (stream 3 1 4 1 5 9 2 5 6) (stream 2 7 1 8 2))
1436=> 1
1437(stream-index = (stream 3 1 4 1 5 9 2 5 6) (stream 2 7 1 8 2))
1438=> #f</enscript>
1439
1440<enscript highlight=scheme filename='stream-ext'>
1441(define (stream-index pred . strs)
1442  (let loop ((strs strs) (pos 0))
1443    (and (not (find stream-null? strs))
1444         (if (apply pred (map stream-car strs))
1445             pos
1446             (loop (map stream-cdr strs) (+ pos 1))))))
1447</enscript>
1448
1449=== stream-member, stream-memq, stream-memv
1450
1451<procedure>(stream-member x str [=])</procedure>
1452<procedure>(stream-memq x str)</procedure>
1453<procedure>(stream-memv x str)</procedure>
1454
1455These procedures return the first substream of the
1456stream {{str}}
1457returned by {{(drop str i)}} for {{i}} less
1458than the length of {{str}} whose stream-car is
1459{{x}}.  If x does not occur in {{str}},
1460then either #f is returned (for finite streams) or this
1461call does not return.  {{stream-memq}} uses {{eq?}}
1462to compare x with the elements of {{str}},
1463while {{stream-memv}} uses {{eqv?}},
1464and stream-member uses {{equal?}}.
1465
1466<enscript highlight=scheme>(stream-memq 'a (stream 'a 'b 'c))
1467=> (a b c)
1468(stream-memq 'b (stream 'a 'b 'c))
1469=> (b c)
1470(stream-memq 'a (stream 'b 'c 'd))
1471=> #f
1472(stream-memq (list 'a) (stream 'b '(a) 'c))
1473=> #f
1474(stream-member (list 'a) (stream 'b '(a) 'c))
1475=> ((a) c)
1476(stream-memq 101 (stream 100 101 102))
1477=> *unspecified*
1478(stream-memv 101 (stream 100 101 102))
1479=> (101 102)</enscript>
1480
1481{{stream-member}} allows the client to pass in an optional equality procedure {{=}}
1482used to compare elements.
1483
1484The comparison procedure is used to compare the elements {{ei}}
1485of {{str}} to the element {{x}} in this way:
1486
1487<enscript highlight=scheme>(= x ei) ; str is (E1 ...)</enscript>
1488
1489That is, the first argument is always {{x}},
1490and the second argument is one of the list elements.
1491Thus one can reliably find the first element of {{str}} that
1492is greater than five with {{(stream-member 5 list <)}}.
1493
1494Note that fully general stream searching may be performed with
1495the {{stream-find-tail}} and {{stream-find}} procedures, e.g.
1496
1497<enscript highlight=scheme>; Find the first pair with an even stream-car:
1498(stream-find-tail even? str)</enscript>
1499
1500<enscript highlight=scheme filename='stream-ext'>
1501(define (stream-member-real x str =)
1502  (stream-find-tail (cut = x <>) str))
1503
1504(define (stream-member x str . rest)
1505  (stream-member-real x str (if (null? rest) equal? (car rest))))
1506
1507(define stream-memq (cut stream-member-real <...> eq?))
1508(define stream-memv (cut stream-member-real <...> eqv?))
1509</enscript>
1510
1511== Sorting
1512
1513=== stream-sort
1514
1515<procedure>(stream-sort str <)</procedure>
1516
1517Returns a copy of {{str}} with its elements sorted.
1518
1519We don't care about the slowness of converting to a list and then back to a
1520stream since
1521
1522* The entire set of elements will be needed in memory and
1523
1524* Sort has greater algorithmical complexity {{O(N) = N*log(N)}}
1525than the conversions.
1526
1527<enscript highlight=scheme filename='stream-ext'>
1528(define (stream-sort stream ord)
1529  (list->stream (sort (stream->list stream) ord)))
1530</enscript>
1531
1532== Strings as streams
1533
1534=== stream-downcase, stream-upcase
1535
1536<procedure>(stream-downcase str)</procedure>
1537<procedure>(stream-upcase str)</procedure>
1538
1539Returns a stream identical to the stream of characters {{str}} but
1540with all characters converted to lowercase or uppercase.
1541
1542<enscript highlight=scheme filename='stream-ext'>
1543(define stream-downcase (cut stream-map char-downcase <>))
1544(define stream-upcase   (cut stream-map char-upcase   <>))
1545</enscript>
1546
1547=== stream-format
1548
1549<procedure>(stream-format fmt ...)</procedure>
1550
1551Does the same as {{(format #f fmt ...)}},
1552but returns the result as a stream of characters rather than a string.
1553
1554<enscript highlight=scheme filename='stream-ext'>
1555(define (stream-format fmt . rest)
1556  (with-output-to-stream
1557    (lambda ()
1558      (format #f fmt rest))))
1559</enscript>
1560
1561=== stream-lines
1562
1563<procedure>(stream-lines str)</procedure>
1564
1565Returns a stream with the lines found in the stream of
1566characters {{str}}.  Each line is itself returned
1567as a stream of characters.  It is an error if {{str}} contains
1568elements that are not characters.
1569
1570<enscript highlight=scheme>(stream-lines (stream #\h #\e #\y #\newline #\y #\o #\u))
1571=> #<stream (#<stream (#\h #\e #\y)> #<stream (#\y #\o #\u)>)></enscript>
1572
1573<enscript highlight=scheme filename='stream-ext'>
1574(define stream-lines (cut stream-split <> (cut equal? <> #\newline)))
1575</enscript>
1576
1577=== stream-unlines
1578
1579TODO: Document
1580
1581<enscript highlight=scheme filename='stream-ext'>
1582(define (stream-unlines lines)
1583  (stream-concatenate (stream-intersperse lines (stream #\newline))))
1584</enscript>
1585
1586== Deletion
1587
1588=== stream-delete
1589
1590<procedure>(stream-delete x str [=])</procedure>
1591
1592{{stream-delete}} returns a stream identical to {{str}}
1593but removing all occurences of the element {{x}}.  The comparison
1594procedure {{=}}, which defaults to {{equal?}}, is used to
1595find them.
1596
1597The stream is not disordered -- elements that appear in the result stream
1598occur in the same order as they occur in the argument stream.
1599
1600Note that fully general element deletion can be performed with the stream-remove procedure, e.g.:
1601
1602<enscript highlight=scheme>;; Delete all the even elements from STR:
1603(stream-remove even? str)</enscript>
1604
1605The comparison procedure is used in this way: {{(= x ei)}}. That
1606is, {{x}} is always the first argument, and a element from the stream
1607is always the second argument.  Thus, one can reliably remove all the numbers
1608greater than five from a stream with {{(delete 5 stream <)}}.
1609
1610<enscript highlight=scheme filename='stream-ext'>
1611(define (stream-delete x str . rest)
1612  (stream-remove
1613    (let ((= (if (null? rest) equal? (car rest))))
1614      (lambda (elt) (= x elt)))
1615    str))
1616</enscript>
1617
1618=== stream-delete-duplicates
1619
1620<procedure>(stream-delete-duplicates str [=])</procedure>
1621
1622{{stream-delete-duplicates}} removes duplicate elements from the
1623{{str}} stream argument.  If there are multiple equal elements in the
1624argument stream, the result stream only contains the first or leftmost of these
1625elements in the result. The order of these surviving elements is the same as in
1626the original stream -- {{stream-delete-duplicates}} does not disorder
1627the stream.
1628
1629The {{=}} parameter is used to compare the elements of the list; it
1630defaults to {{equal?}}. If {{x}} comes before {{y}}
1631in list, then the comparison is performed {{(= x y)}}.  The comparison
1632procedure will be used to compare each pair of elements in list no more than
1633once; the order in which it is applied to the various pairs is not
1634specified.
1635
1636Be aware that, in general, {{stream-delete-duplicates}} runs in time O(n2) for
1637n-streams lists. Uniquifying long lists can be accomplished in O(n lg n) time
1638by sorting the stream to bring equal elements together, then using a linear-time
1639algorithm to remove equal elements. Alternatively, one can use algorithms based
1640on element-marking, with linear-time results.
1641
1642Also note that a list might be kept in memory with the entire contents
1643of the stream during the execution of calls to this function.
1644
1645<enscript highlight=scheme>(stream-delete-duplicates (stream 0 1 0 3 0 1 3 4))
1646=> #<stream (0 1 3 4)></enscript>
1647
1648<enscript highlight=scheme filename='stream-ext'>
1649(define (stream-delete-duplicates str . rest)
1650  (stream-delete-dups str '() (if (null? rest) equal? (car rest))))
1651
1652(define (stream-delete-dups str already =)
1653  (stream-delay
1654    (cond
1655      ((stream-null? str) stream-null)
1656      ((any (lambda (x) (= x (stream-car str))) already)
1657       (stream-delete-dups (stream-cdr str) already =))
1658      (else
1659        (stream-cons (stream-car str)
1660                     (stream-delete-dups (stream-cdr str) (cons (stream-car str) already) =))))))
1661</enscript>
1662
1663== Other undocumented code
1664
1665The following procedures are also provided.
1666
1667TODO: Move them to the appropriate sections in this document and get rid of this section.
1668
1669<enscript highlight=scheme filename='stream-ext'>
1670(define (stream-convert-safe check? convert)
1671  (lambda (obj)
1672    (if (check? obj)
1673      (convert obj)
1674      obj)))
1675
1676(define (stream-wrap-proc-generic convert-inputs convert-outputs)
1677  (lambda (proc)
1678    (lambda args
1679      (receive results
1680               (apply proc (map convert-inputs args))
1681        (apply values (map convert-outputs results))))))
1682
1683(define stream-wrap-proc-string
1684  (stream-wrap-proc-generic
1685    (stream-convert-safe stream? stream->string)
1686    (stream-convert-safe string? string->stream)))
1687
1688(define stream-wrap-proc-list
1689  (stream-wrap-proc-generic
1690    (stream-convert-safe stream? stream->list)
1691    (stream-convert-safe list? list->stream)))
1692
1693(define stream-wrap-proc-stream
1694  (stream-wrap-proc-generic
1695    (lambda (obj)
1696      (cond
1697        ((list? obj) (list->stream obj))
1698        ((string? obj) (string->stream obj))
1699        (else obj)))
1700    identity))
1701
1702;;; Pattern Matching
1703
1704(define (stream-grep re stream)
1705  (let ((real-re (if (string? re) (regexp re) re)))
1706    (stream-filter (cut string-match real-re <>) stream)))
1707
1708; (equal? tail stream-null) rather than (stream-null? tail) to avoid an
1709; off-by-one error (evaluating tail before obj is fully consumed).
1710
1711(define (->stream-char obj . rest)
1712  (stream-delay
1713   (let-optionals rest ((tail stream-null))
1714     (cond
1715      ((string? obj) (string->stream obj tail))
1716      ((or (number? obj) (boolean? obj) (symbol? obj)) (->stream-char (->string obj) tail))
1717      ((char? obj) (stream-cons obj tail))
1718      ((port? obj) (port->stream obj))
1719      ((stream? obj)
1720       (if (equal? tail stream-null)
1721           obj
1722           (stream-append obj tail)))
1723      (else (error "Unable to convert object to stream-char" obj))))))
1724
1725(define (stream-replace in reps)
1726  (if (stream-null? in)
1727      stream-null
1728      (let ((obj (assoc (stream-car in) reps)))
1729        (if obj
1730            (->stream-char (cadr obj) (stream-replace (stream-cdr in) reps))
1731            (stream-cons (stream-car in) (stream-replace (stream-cdr in) reps))))))
1732
1733(define (stream-translate str from to)
1734  (stream-map (lambda (c) (if (equal? c from) to c)) str))
1735</enscript>
1736
1737== Version History
1738
1739;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.
1740;1.5: Build script now uses exports.
1741;1.4.1: Small bug fix in {{stream-fold-right}}.
1742;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.
1743;1.3.1: Replaced use of {{(end-of-file)}} with {{#!eof}}
1744;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}}.
1745;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}}.
1746;1.1 : Removed {{stream-filter}} (it's provided by srfi-40).
1747;1.0 : First public release.
Note: See TracBrowser for help on using the repository browser.