source: project/wiki/stream-ext @ 12749

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

Changes applied for azul (193.142.125.1) through svnwiki:

Adding more info

File size: 55.2 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
451Calls the procedure {{proc}} with no arguments, with its {{current-input-port}}
452bound to a port created from the stream of characters {{stream}}.
453
454<examples testgroup='with-input-from-stream' filename='stream-ext'>
455
456<example>
457<expr>(with-input-from-stream (stream #\" #\a #\b #\c #\") read)</expr>
458<result>"abc"</result>
459</example>
460
461</examples>
462
463The stream will only be evaluated as the input is consumed by the
464procedure.
465
466<enscript highlight=scheme filename='stream-ext'>
467(define (with-input-from-stream stream proc)
468  (with-input-from-port
469    (make-input-port
470      (lambda ()
471        (if (stream-null? stream)
472          #!eof
473          (let ((char (stream-car stream)))
474            (set! stream (stream-cdr stream))
475            char)))
476      (lambda ()
477        (not (stream-null? stream)))
478      (lambda ()
479        (set! stream stream-null))
480      (lambda ()
481        (stream-car stream)))
482    proc))
483</enscript>
484
485=== write-stream
486
487<procedure>(write-stream stream [port [writer]])</procedure>
488
489Write all the elements in the stream {{stream}} to the output port {{port}},
490which defaults to the current output port.
491If the stream is infinite, this function does not return.
492
493{{writer}} is the procedure used to write individual
494elements to the port.  It should receive the element to be written
495and the output port as its only arguments.  The default value is {{write-char}}
496but {{write}} and {{write-line}} can also be used (depending
497on the contents of {{stream}}).
498
499<enscript highlight=scheme filename='stream-ext'>
500(define (write-stream stream . rest)
501  (let-optionals rest ((port (current-output-port)) (writer write-char))
502    (let loop ((s stream))
503      (unless (stream-null? s)
504        (writer (stream-car s) port)
505        (loop (stream-cdr s))))))
506</enscript>
507
508== Predicates
509
510=== stream=
511
512<procedure>(stream= elt= str1 ...)</procedure>
513
514Determines stream equality, given an element-equality procedure.
515Stream {{A}} equals stream {{B}} if they are of the
516same length, and their corresponding elements are equal, as determined
517by {{elt=}}.
518If the element-comparison procedure's first argument is from stri,
519then its second argument is from stri+1, i.e. it is always called
520as {{(elt= a b)}} for {{a}} an element of stream {{A}},
521and {{b}} an element of stream {{B}}.
522
523In the n-ary case, every {{stri}} is compared to {{stri+1}}
524(as opposed, for example, to comparing {{str1}} to every {{stri}},
525for {{i}} > 1).
526If there are no list arguments at all, {{stream=}} simply returns true.
527
528The dynamic order in which the {{elt=}} procedure is applied to pairs of
529elements is not specified. For example, if {{stream=}} is applied to three lists,
530{{A}}, {{B}},
531and {{C}}, it may first completely compare
532{{A}} to {{B}},
533then compare {{B}} to {{C}}, or it may
534compare the first elements of {{A}} and {{B}},
535then the first elements of {{B}} and {{C}},
536then the second elements of {{A}} and {{B}}, and so forth.
537
538The equality procedure must be consistent with {{eq?}}.
539That is, it must be the case that:
540
541<enscript highlight=scheme>(eq? x y) => (elt= x y)</enscript>
542
543This implies that two lists which are {{eq?}} are always {{stream=}}
544as well; implementations may exploit this fact to "short-cut" the element-by-element comparisons.
545
546<enscript highlight=scheme>(stream= eq?)
547=> #t       ; Trivial cases
548(stream= eq? (stream 0 1 2))
549=> #t</enscript>
550
551<enscript highlight=scheme filename='stream-ext'>
552(define (stream= elt= . strs)
553  (or (every stream-null? strs)
554      (and (not (any stream-null? strs))
555           (let loop ((es (map stream-car strs)))
556             (or (null? (cdr es))
557                 (and (elt= (car es) (cadr es)) (loop (cdr es)))))
558           (apply stream= elt= (map stream-cdr strs)))))
559</enscript>
560
561=== stream-prefix=
562
563<procedure>(stream-prefix= str prefix [=])</procedure>
564
565Evaluates whether the elements at the beginning of stream
566{{str}} are equal to the elements in the list
567{{prefix}}.
568
569{{eq}} is the function used to compare the individual elements.
570The default is {{equal?}}.
571
572If the prefix of the stream matches {{prefix}}, the
573function returns the contents of {{stream}} following
574it.  False is returned otherwise.
575
576<enscript highlight=scheme>(stream-prefix= (stream 1 2 3 4) '(1 2))
577=> #<stream (3 4)>
578(stream-prefix= (stream 1 2 3 4) '(1 3))
579=> #f</enscript>
580
581<enscript highlight=scheme filename='stream-ext'>
582(define (stream-prefix= str prefix . rest)
583  (if (null? prefix)
584    str
585    (and (not (stream-null? str))
586         ((if (null? rest) equal? (car rest)) (stream-car str) (car prefix))
587         (apply stream-prefix= (stream-cdr str) (cdr prefix) rest))))
588</enscript>
589
590=== stream>, stream<
591
592...
593
594<enscript highlight=scheme filename='stream-ext'>
595(define (stream< elt< . strs)
596  (or (null? strs)
597      (null? (cdr strs))
598      (and
599        (let loop ((a (car strs)) (b (cadr strs)))
600          (or (elt< (stream-car a) (stream-car b))
601              (and (not (elt< (stream-car b) (stream-car a)))
602                   (loop (stream-cdr a) (stream-cdr b)))))
603        (apply stream< elt (cdr strs)))))
604
605(define (stream> elt< . strs) (apply stream< (complement elt<) strs))
606</enscript>
607
608== Selectors
609
610=== stream-caar ... stream-cddddr
611
612<procedure>(stream-caar stream)</procedure>
613<procedure>(stream-cadr stream)</procedure>
614<procedure>(stream-cdar stream)</procedure>
615<procedure>(stream-cddr stream)</procedure>
616
617<procedure>(stream-caaar stream)</procedure>
618<procedure>(stream-caadr stream)</procedure>
619<procedure>(stream-cadar stream)</procedure>
620<procedure>(stream-caddr stream)</procedure>
621<procedure>(stream-cdaar stream)</procedure>
622<procedure>(stream-cdadr stream)</procedure>
623<procedure>(stream-cddar stream)</procedure>
624<procedure>(stream-cdddr stream)</procedure>
625
626<procedure>(stream-caaaar stream)</procedure>
627<procedure>(stream-caaadr stream)</procedure>
628<procedure>(stream-caadar stream)</procedure>
629<procedure>(stream-caaddr stream)</procedure>
630<procedure>(stream-cadaar stream)</procedure>
631<procedure>(stream-cadadr stream)</procedure>
632<procedure>(stream-caddar stream)</procedure>
633<procedure>(stream-cadddr stream)</procedure>
634<procedure>(stream-cdaaar stream)</procedure>
635<procedure>(stream-cdaadr stream)</procedure>
636<procedure>(stream-cdadar stream)</procedure>
637<procedure>(stream-cdaddr stream)</procedure>
638<procedure>(stream-cddaar stream)</procedure>
639<procedure>(stream-cddadr stream)</procedure>
640<procedure>(stream-cdddar stream)</procedure>
641<procedure>(stream-cddddr stream)</procedure>
642
643These procedures are compositions of
644{{stream-car}} and {{stream-cdr}},
645where for example {{stream-caddr}} could be defined by:
646
647<enscript highlight=scheme>(define (stream-caddr x) (stream-car (stream-cdr (stream-cdr x))))</enscript>
648
649Arbitrary compositions, up to four deep, are provided.
650There are twenty-eight of these procedures in all.
651
652<enscript highlight=scheme filename='stream-ext'>
653(define stream-caar   (compose stream-car stream-car))
654(define stream-cadr   (compose stream-car stream-cdr))
655(define stream-cdar   (compose stream-cdr stream-car))
656(define stream-cddr   (compose stream-cdr stream-cdr))
657
658(define stream-caaar  (compose stream-caar stream-car))
659(define stream-caadr  (compose stream-caar stream-cdr))
660(define stream-cadar  (compose stream-cadr stream-car))
661(define stream-caddr  (compose stream-cadr stream-cdr))
662(define stream-cdaar  (compose stream-cdar stream-car))
663(define stream-cdadr  (compose stream-cdar stream-cdr))
664(define stream-cddar  (compose stream-cddr stream-car))
665(define stream-cdddr  (compose stream-cddr stream-cdr))
666
667(define stream-caaaar (compose stream-caaar stream-car))
668(define stream-caaadr (compose stream-caaar stream-cdr))
669(define stream-caadar (compose stream-caadr stream-car))
670(define stream-caaddr (compose stream-caadr stream-cdr))
671(define stream-cadaar (compose stream-cadar stream-car))
672(define stream-cadadr (compose stream-cadar stream-cdr))
673(define stream-caddar (compose stream-caddr stream-car))
674(define stream-cadddr (compose stream-caddr stream-cdr))
675(define stream-cdaaar (compose stream-cdaar stream-car))
676(define stream-cdaadr (compose stream-cdaar stream-cdr))
677(define stream-cdadar (compose stream-cdadr stream-car))
678(define stream-cdaddr (compose stream-cdadr stream-cdr))
679(define stream-cddaar (compose stream-cddar stream-car))
680(define stream-cddadr (compose stream-cddar stream-cdr))
681(define stream-cdddar (compose stream-cdddr stream-car))
682(define stream-cddddr (compose stream-cdddr stream-cdr))
683</enscript>
684
685=== stream-ref
686
687<procedure>(stream-ref str pos)</procedure>
688
689Returns the element in the stream {{str}} at the
690position {{pos}}.  This is the same as the stream-car
691of {{(stream-drop str pos)}}. It is an error if
692{{str}} has {{pos}} or fewer elements.
693
694<enscript highlight=scheme>(stream-ref (stream 0 1 2 3 4 5) 3)
695=> 3</enscript>
696
697<enscript highlight=scheme filename='stream-ext'>
698(define (stream-ref str pos)
699  (if (zero? pos)
700      (stream-car str)
701      (stream-ref (stream-cdr str) (- pos 1))))
702</enscript>
703
704=== stream-first ... stream-tenth
705
706<procedure>(stream-first str)</procedure>
707<procedure>(stream-second str)</procedure>
708<procedure>(stream-third str)</procedure>
709<procedure>(stream-fourth str)</procedure>
710<procedure>(stream-fifth str)</procedure>
711<procedure>(stream-sixth str)</procedure>
712<procedure>(stream-seventh str)</procedure>
713<procedure>(stream-sixth str)</procedure>
714<procedure>(stream-eighth str)</procedure>
715<procedure>(stream-tenth str)</procedure>
716
717Synonyms for {{(stream-car str)}},
718{{(stream-cadr str)}}, {{(stream-caddr str)}}, ...
719
720<enscript highlight=scheme>(stream-third (stream 0 1 2 3 4))
721=> 2</enscript>
722
723<enscript highlight=scheme filename='stream-ext'>
724(define stream-first   stream-car)
725(define stream-second  stream-cadr)
726(define stream-third   stream-caddr)
727(define stream-fourth  stream-cadddr)
728(define stream-fifth   (compose stream-car    stream-cddddr))
729(define stream-sixth   (compose stream-cadr   stream-cddddr))
730(define stream-seventh (compose stream-caddr  stream-cddddr))
731(define stream-eighth  (compose stream-cadddr stream-cddddr))
732(define stream-ninth   (compose stream-car    stream-cddddr stream-cddddr))
733(define stream-tenth   (compose stream-cadr   stream-cddddr stream-cddddr))
734</enscript>
735
736=== stream-take, stream-take-safe
737
738<procedure>(stream-take str count)</procedure>
739<procedure>(stream-take-safe str count)</procedure>
740
741Returns a stream with the first {{count}} elements
742in stream {{str}}.  For {{stream-take}}, it is an error if {{str}}
743has fewer than {{count}} elements; for {{stream-take-safe}}, {{str}}
744will be returned.
745
746<enscript highlight=scheme>(stream-take (stream 1 2 3 4 5) 2)
747=> #<stream (1 2)></enscript>
748
749<enscript highlight=scheme filename='stream-ext'>
750(define (stream-take stream count)
751  (stream-delay
752   (if (zero? count)
753       stream-null
754       (stream-cons (stream-car stream)
755                    (stream-take (stream-cdr stream) (- count 1))))))
756
757(define (stream-take-safe stream count)
758  (stream-delay
759    (if (or (zero? count) (stream-null? stream))
760      stream-null
761      (stream-cons (stream-car stream)
762                   (stream-take-safe (stream-cdr stream) (- count 1))))))
763</enscript>
764
765=== stream-drop, stream-drop-safe
766
767<procedure>(stream-drop str count)</procedure>
768<procedure>(stream-drop-safe str count)</procedure>
769
770Returns the sub-stream of {{str}} obtained by omitting
771the first {{count}} elements.  For {{stream-drop}}, it is an error if {str}} has
772fewer than {{count}} elements; for {{stream-drop-safe}}, the empty stream
773will be returned.
774
775<enscript highlight=scheme>(stream-drop (stream 0 1 2 3 4 5) 3)
776=> #<stream (3 4 5)></enscript>
777
778<enscript highlight=scheme filename='stream-ext'>
779(define (stream-drop str count)
780  (stream-delay
781   (if (zero? count)
782       str
783       (stream-drop (stream-cdr str) (- count 1)))))
784
785(define (stream-drop-safe str count)
786  (stream-delay
787    (if (or (zero? count) (stream-null? str))
788      str
789      (stream-drop-safe (stream-cdr str) (- count 1)))))
790
791
792
793</enscript>
794
795=== stream-intersperse
796
797<procedure>(stream-intersperse stream element)</procedure>
798
799Returns a new stream with the elements in the stream {{stream}}
800but placing {{element}} between each.
801
802<enscript highlight=scheme>(stream-intersperse (stream 0 1 2 3) #f)
803=> #<stream (0 #f 1 #f 2 #f 3)>
804(stream-intersperse (stream 0) 1)
805=> #<stream (0)></enscript>
806
807<enscript highlight=scheme filename='stream-ext'>
808(define (stream-intersperse stream element . rest)
809  (let-optionals rest ((tail stream-null))
810    (stream-delay
811      (if (stream-null? stream)
812        tail
813        (stream-cons (stream-car stream)
814          (let loop ((rest (stream-cdr stream)))
815            (if (stream-null? rest)
816              tail
817              (stream-cons element (stream-cons (stream-car rest) (loop (stream-cdr rest)))))))))))
818</enscript>
819
820=== stream-split
821
822<procedure>(stream-split str pred)</procedure>
823
824Splits the stream {{str}} into multiple streams, removing
825the elements satisfying predicate {{pred}}.
826This is similar to what {{string-split}} does
827but operates on streams (rather than strings) and returns the result
828as a stream of streams (rather than a list of strings).
829
830Example:
831
832<enscript highlight=scheme>(stream-split (stream 1 2 3 5 7 8 9 10) even?)
833=> #<stream (#<stream (1)> #<stream (3 5 7)> #<stream (9)>)></enscript>
834
835<enscript highlight=scheme filename='stream-ext'>
836(define (stream-split in p?)
837  (let loop ((current '()) (s in))
838    (stream-delay
839      (cond
840        ((stream-null? s)
841           (if (null? current)
842             stream-null
843             (stream-cons (list->stream (reverse current)) stream-null)))
844        ((p? (stream-car s))
845           (stream-cons (list->stream (reverse current)) (loop '() (stream-cdr s))))
846        (else (loop (cons (stream-car s) current) (stream-cdr s)))))))
847</enscript>
848
849=== stream-last
850
851<procedure>(stream-last str)</procedure>
852
853Returns the last element of the non-empty finite stream {{str}}.
854It is an error to pass an empty stream.
855
856<enscript highlight=scheme>(stream-last (stream 'a 'b 'c))
857=> c</enscript>
858
859{{stream-last}} could be defined as:
860
861<enscript highlight=scheme>(define (stream-last stream)
862  (stream-car (stream-last-n stream 1)))</enscript>
863
864<enscript highlight=scheme filename='stream-ext'>
865(define (stream-last str)
866  (if (stream-null? (stream-cdr str))
867    (stream-car str)
868    (stream-last (stream-cdr str))))
869</enscript>
870
871=== stream-last-n
872
873<rocedure>(stream-last-n stream count)</procedure>
874
875Returns a stream with the last {{count}}
876elements of the finite stream {{str}}.  If fewer
877than {{count}} elements are available in {{stream}},
878{{stream}} itself is returned.
879
880<enscript highlight=scheme>(stream-null? (stream-last-n (stream #\a #\b #\c #\d) 0))
881=> #t
882(stream-last-n (stream #\a #\b #\c #\d) 1)
883=> #<stream (#\d)>
884(stream-last-n (stream #\a #\b #\c #\d) 3)
885=> #<stream (#\b #\c #\d)>
886(stream-last-n (stream #\a #\b #\c #\d) 20)
887=> #<stream (#\a #\b #\c #\d)></enscript>
888
889<enscript highlight=scheme filename='stream-ext'>
890(define (stream-last-n str count)
891  (stream-delay
892    (let ((l (list #f)))
893      (set-cdr! l l)
894      (let loop ((s str) (l l) (i 0))
895        (cond
896          ((stream-null? s)
897           (if (< i count)
898             str
899             (stream-take (list->stream (cdr l)) i)))
900          ((equal? i count)
901             (set-car! l (stream-car s))
902             (loop (stream-cdr s) (cdr l) i))
903          (else
904            (set-car! l (stream-car s))
905            (set-cdr! l (cons i (cdr l)))
906            (loop (stream-cdr s) (cdr l) (+ i 1))))))))
907</enscript>
908
909=== stream-butlast
910
911<procedure>(stream-butlast stream)</procedure>
912
913Returns a stream with all the elements in the
914non-empty stream {{str}} except the last.
915The order of the elements is respected.
916
917<enscript highlight=scheme>(stream-butlast (stream #\a #\b #\c))
918=> #<stream (#\a #\b)></enscript>
919
920{{stream-butlast}} can be defined as:
921
922<enscript highlight=scheme filename='stream-ext'>
923(define (stream-butlast str)
924  (stream-butlast-n str 1))
925</enscript>
926
927=== stream-butlast-n
928
929<procedure>(stream-butlast-n stream count)</procedure>
930
931Returns a stream with all the elements in the
932stream {{stream}} except the last
933{{count}}.  The order of the elements is
934respected.  It is an error if {{stream}}
935has fewer than {{count}} elements.
936
937<enscript highlight=scheme>(stream-butlast-n (stream #\a #\b #\c) 2)
938=> #<stream (#\a)>
939(stream-null? (stream-butlast-n (stream #\a #\b #\c) 3))
940=> #t</enscript>
941
942<enscript highlight=scheme filename='stream-ext'>
943(define (stream-butlast-n str count)
944  (stream-delay
945    (let loop ((head str) (tail (stream-drop str count)))
946      (if (stream-null? tail)
947        stream-null
948        (stream-cons (stream-car head) (loop (stream-cdr head) (stream-cdr tail)))))))
949</enscript>
950
951== Miscellaneous: length, append, concatenate, reverse, zip & count
952
953=== stream-length
954
955<procedure>(stream-length str)</procedure>
956
957Returns the length of the argument stream (a non-negative integer n such that
958stream-cdr applied n times to the stream produces the null stream).
959
960This function does not return when {{str}} is an
961infinite streams.
962
963Returns the length of the stream {{str}}.
964This call does not return if {{str}} is an
965infinite stream.
966
967<enscript highlight=scheme>(stream-length (stream 0 1 2 3))
968=> 4</enscript>
969
970<enscript highlight=scheme filename='stream-ext'>
971(define (stream-length str)
972  (let loop ((i 0) (s str))
973    (if (stream-null? s)
974        i
975        (loop (+ i 1) (stream-cdr s)))))
976</enscript>
977
978=== stream-length>=
979
980<procedure>(stream-length>= str len)</procedure>
981
982Returns {{#t}} if the length of the stream {{str}}
983is greater or equal than {{len}}, {{#f}} otherwise.
984
985For finite streams, this is equivalent, albeit faster (specially when
986{{len}} is significantly smaller than the length of {{str}}), to:
987
988<enscript highlight=scheme>(>= (stream-length str) len)</enscript>
989
990However, for infinite streams it is equivalent to {{#t}}
991(whereas the above code would never terminate).
992
993<enscript highlight=scheme filename='stream-ext'>
994(define (stream-length>= str len)
995  (or (zero? len)
996      (and (not (stream-null? str))
997           (stream-length>= (stream-cdr str) (- len 1)))))
998</enscript>
999
1000=== stream-append
1001
1002<procedure>(stream-append str1 str2 ...)</procedure>
1003
1004{{stream-append}} returns a stream consisting of the elements of str1
1005followed by the elements of the other stream parameters.
1006
1007<enscript highlight=scheme>(stream-append (stream 1) (stream 2))
1008=> #<stream (1 2)>
1009(stream-append (stream 1) (stream 2 3 4))
1010=> #<stream (1 2 3 4)>
1011(stream-append (stream 'a '(b)) (stream '(c)))
1012=> #<stream (a (b) (c))></enscript>
1013
1014<enscript highlight=scheme filename='stream-ext'>
1015(define (stream-append . strs)
1016  (stream-delay
1017    (cond
1018      ((null? strs) stream-null)
1019      ((null? (cdr strs)) (car strs))
1020      (else
1021        (let loop ((c (car strs)) (rest (cdr strs)))
1022          (stream-delay
1023            (if (stream-null? c)
1024              (apply stream-append rest)
1025              (stream-cons (stream-car c) (loop (stream-cdr c) rest)))))))))
1026</enscript>
1027
1028=== stream-concatenate
1029
1030<procedure>(stream-concatenate str)</procedure>
1031
1032...
1033
1034<enscript highlight=scheme filename='stream-ext'>
1035(define (stream-concatenate strs)
1036  (stream-delay
1037    (if (stream-null? strs)
1038      stream-null
1039      (stream-append (stream-car strs) (stream-concatenate (stream-cdr strs))))))
1040</enscript>
1041
1042=== stream-reverse
1043
1044<procedure>(stream-reverse str)</procedure>
1045
1046{{stream-reverse}}
1047returns a stream consisting of the elements of
1048the stream {{str}} in reverse order.
1049
1050This procedure does not return if {{str}} is an infinite
1051stream.
1052
1053<enscript highlight=scheme>(stream-reverse (stream 1 2 3))
1054=> #<stream (3 2 1)>
1055(stream-reverse (stream 'a '(b c) 'd '(e (f))))
1056=> #<stream ((e (f)) d (b c) a)></enscript>
1057
1058<enscript highlight=scheme filename='stream-ext'>
1059(define (stream-reverse str . args)
1060  (stream-delay
1061    (let-optionals args ((tail stream-null))
1062      (let loop ((head str) (tail tail))
1063        (if (stream-null? head)
1064          tail
1065          (loop (stream-cdr head) (stream-cons (stream-car head) tail)))))))
1066</enscript>
1067
1068=== stream-count
1069
1070<procedure>(stream-count pred str1 str2 ...)</procedure>
1071
1072{{pred}} is a procedure taking as many arguments as there are streams and
1073returning a single value. It is applied element-wise to the elements of the
1074streams, and a count is tallied of the number of elements that produce a true
1075value. This count is returned. count is "iterative" in that it is guaranteed to
1076apply {{pred}} to the stream elements in a left-to-right order. The counting stops
1077when the shortest list expires.
1078
1079If all the streams are infinite, this procedure does not return.
1080
1081<enscript highlight=scheme>(stream-count even? (stream 3 1 4 1 5 9 2 5 6))
1082=> 3
1083(stream-count < (stream 1 2 4 8) (stream 2 4 6 8 10 12 14 16))
1084=> 3
1085(stream-count < (stream 3 1 4 1) (make-stream #t 2))
1086=> 2</enscript>
1087
1088<enscript highlight=scheme filename='stream-ext'>
1089(define (stream-count pred . strs)
1090  (apply
1091    stream-fold
1092    (lambda args
1093      (+ (last args)
1094         (if (apply pred (butlast args)) 1 0)))
1095    0
1096    strs)
1097</enscript>
1098
1099== Fold
1100
1101=== stream-fold
1102
1103...
1104
1105<enscript highlight=scheme filename='stream-ext'>
1106(define (stream-fold func nil . strs)
1107  (if (any stream-null? str)
1108    nil
1109    (apply
1110      stream-fold
1111      func
1112      (apply (cut func <...> nil) (map stream-car strs))
1113      (map stream-cdr strs))))
1114</enscript>
1115
1116=== stream-fold-right
1117
1118...
1119
1120<enscript highlight=scheme filename='stream-ext'>
1121(define (stream-fold-right func nil str)
1122  (if (stream-null? str)
1123    nil
1124    (func (stream-car str) (stream-fold-right func nil (stream-cdr str)))))
1125</enscript>
1126
1127=== stream-fold-right-delay
1128
1129...
1130
1131Similar to {{stream-fold-right}}, but useful when the result of the folding
1132procedure is a stream; in this case, the evaluation of the fold is done in a
1133lazy manner.
1134
1135<enscript highlight=scheme filename='stream-ext'>
1136(define (stream-fold-right-delay func nil str)
1137  (stream-delay
1138    (if (stream-null? str)
1139      nil
1140      (func (stream-car str) (stream-fold-right-delay func nil (stream-cdr str))))))
1141</enscript>
1142
1143== Filtering & Partitioning
1144
1145=== stream-partition
1146
1147<procedure>(stream-partition pred str)</procedure>
1148
1149Partitions the elements of stream {{str}} with predicate
1150{{pred}}, and returns two values: the stream of in-elements
1151and the stream of out-elements.
1152The stream is not disordered -- elements occur in the result streams
1153in the same order as they occur in the argument stream.
1154
1155The dynamic order in which the various applications of {{pred}}
1156depends on the evaluation of the streams.  {{pred}} might be evaluated
1157twice for each element in the argument stream.
1158
1159<enscript highlight=scheme>(stream-partition symbol? (stream 'one 2 3 'four 'five 6))
1160=>
1161   #<stream (one four five)>
1162   #<stream (2 3 6)></enscript>
1163
1164<enscript highlight=scheme filename='stream-ext'>
1165(define (stream-partition pred str)
1166  (values (stream-filter pred str)
1167          (stream-remove pred str)))
1168</enscript>
1169
1170=== stream-remove
1171
1172<procedure>(stream-remove pred str)</procedure>
1173
1174Returns a stream with all the elements in the stream {{str}}
1175except those that satisfy predicate pred:
1176
1177<enscript highlight=scheme>(lambda (pred str) (stream-filter (lambda (x) (not (pred x))) str))</enscript>
1178
1179The stream is not disordered -- elements that appear in the result list
1180occur in the same order as they occur in the argument list.
1181
1182<enscript highlight=scheme>(stream-remove even? (stream 0 7 8 8 43 -4))
1183=> #<stream (7 43)></enscript>
1184
1185<enscript highlight=scheme filename='stream-ext'>
1186(define (stream-remove pred str)
1187  (stream-filter (complement pred) str))
1188</enscript>
1189
1190== Searching
1191
1192=== stream-find
1193
1194<procedure>(stream-find pred str)</procedure>
1195
1196Return the first element of the stream {{str}}
1197that satisfies predicate {{pred}};
1198false if no element does.
1199
1200<enscript highlight=scheme>(stream-find even? (stream 3 1 4 1 5 9))
1201=> 4</enscript>
1202
1203Note that {{stream-find}} has an ambiguity in
1204its lookup semantics -- if find returns {{#f}},
1205you cannot tell (in general) if it found a {{#f}} element that
1206satisfied {{pred}}, or if it did not find any element at all.
1207In many situations, this ambiguity cannot arise -- either the list
1208being searched is known not to contain any {{#f}} elements, or the
1209list is guaranteed to have an element satisfying {{pred}}.
1210However, in cases where this ambiguity can arise, you should use
1211{{stream-find-tail}} instead of {{stream-find}}
1212-- {{stream-find-tail}} has no such ambiguity:
1213
1214<enscript highlight=scheme>(cond ((stream-find-tail pred lis) => (lambda (pair) ...)) ; Handle (CAR PAIR)
1215      (else ...)) ; Search failed.</enscript>
1216
1217<enscript highlight=scheme filename='stream-ext'>
1218(define (stream-find pred str)
1219  (let ((result (stream-find-tail pred str)))
1220    (and result (stream-car result))))
1221</enscript>
1222
1223=== stream-find-tail
1224
1225<procedure>(stream-find-tail pred str)</procedure>
1226
1227Returns the first stream-pair of {{str}}
1228whose car satisfies predicate {{pred}}.
1229If no pair does, returns false.
1230
1231<enscript highlight=scheme>(stream-find-tail even? (stream 3 1 37 -8 -5 0 0))
1232=> #<stream (-8 -5 0 0)>
1233(stream-find-tail even? (stream 3 1 37 -5))
1234=> #f</enscript>
1235
1236{{stream-find-tail}} can be viewed as a general-predicate
1237variant of the {{stream-member}} function.  {{stream-member}}
1238can be defined as a call to stream-find-tail:
1239
1240<enscript highlight=scheme>;; (stream-member x str):
1241(stream-find-tail (lambda (elt) (equal? x elt)) str)</enscript>
1242
1243Find-tail is essentially stream-drop-while, where the sense of the
1244predicate is inverted: Find-tail searches until it finds an element
1245satisfying the predicate; drop-while searches until it finds an
1246element that doesn't satisfy the predicate.
1247
1248<enscript highlight=scheme filename='stream-ext'>
1249(define (stream-find-tail pred str)
1250  (and (not (stream-null? str))
1251       (if (pred (stream-car str))
1252           str
1253           (stream-find-tail pred (stream-cdr str)))))
1254</enscript>
1255
1256=== stream-take-while
1257
1258<procedure>(stream-take-while pred str)</procedure>
1259
1260Returns the longest initial prefix of stream {{str}}
1261whose elements all satisfy the predicate {{pred}}.
1262
1263<enscript highlight=scheme>(stream-take-while even? (stream 2 18 3 10 22 9))
1264=> #<stream (2 18)></enscript>
1265
1266<enscript highlight=scheme filename='stream-ext'>
1267(define (stream-take-while pred str)
1268  (stream-delay
1269   (if (or (stream-null? str) (not (pred (stream-car str))))
1270       stream-null
1271       (stream-cons (stream-car str)
1272         (stream-take-while pred (stream-cdr str))))))
1273</enscript>
1274
1275=== stream-drop-while
1276
1277<procedure>(stream-drop-while pred str)</procedure>
1278
1279Drops the longest initial prefix of stream {{str}} whose
1280elements all satisfy the predicate {{pred}} and returns
1281the rest of the stream.
1282
1283<enscript highlight=scheme>(stream-drop-while even? (stream 2 18 3 10 22 9))
1284=> #<stream (3 10 22 9)></enscript>
1285
1286<enscript highlight=scheme filename='stream-ext'>
1287(define (stream-drop-while pred str)
1288  (stream-delay
1289   (if (or (stream-null? str) (not (pred (stream-car str))))
1290       str
1291       (stream-drop-while pred (stream-cdr str)))))
1292</enscript>
1293
1294=== stream-span, stream-break
1295
1296<procedure>(stream-span pred str)</procedure>
1297<procedure>(stream-break pred str)</procedure>
1298
1299{{stream-span}} splits the stream {{str}} into the longest
1300initial prefix whose elements all satisfy predicate {{pred}}, and the
1301remaining tail.  {{stream-break}} inverts the sense of the predicate:
1302the tail commences with the first element of the input list that satisfies the
1303predicate.
1304
1305In other words: {{stream-span}} finds the intial span of elements
1306satisfying {{pred}}, and {{stream-break}} breaks the list at
1307the first element not satisfying {{pred}}.
1308
1309stream-span is equivalent to:
1310
1311<enscript highlight=scheme>(values (stream-take-while pred str) (stream-drop-while pred str))</enscript>
1312
1313Examples:
1314
1315<enscript highlight=scheme>(stream-span even? (stream 2 18 3 10 22 9))
1316=>
1317  #<stream (2 18)>
1318  #<stream (3 10 22 9)>
1319(stream-break even? (stream 3 1 4 1 5 9))
1320=>
1321  #<stream (3 1)>
1322  #<stream (4 1 5 9)></enscript>
1323
1324<enscript highlight=scheme filename='stream-ext'>
1325(define (stream-span pred str)
1326  (values (stream-take-while pred str) (stream-drop-while pred str)))
1327
1328(define (stream-break pred str)
1329  (stream-span (complement pred) str))
1330</enscript>
1331
1332=== stream-any
1333
1334<procedure>(stream-any pred str1 str2 ...)</procedure>
1335
1336Applies the predicate {{pred}}
1337across the streams {{str1 ... strn}},
1338returning true if the predicate returns true on any application.
1339
1340If there are {{n}} stream arguments
1341{{str1 ... strn}}, then {{pred}}
1342must be a procedure taking {{n}} arguments
1343and returning a boolean result.
1344
1345{{stream-any}} applies {{pred}} to the first
1346elements of the {{stri}} parameters.
1347If this application returns a true value, {{stream-any}}
1348immediately returns that value. Otherwise, it iterates, applying
1349{{pred}} to the second elements of the {{stri}}
1350parameters, then the third, and so forth. The iteration stops when
1351a true value is produced or one of the streams runs out of values;
1352in the latter case, {{stream-any}} returns #f.
1353
1354Just like with {{any}} (see SRFI-1), it would be desirable
1355to make the last call to {{pred}} a tail call.  However,
1356this would force {{stream-any}} to evaluate streams in
1357advance.  For this reason, the last call to {{pred}} is
1358not a tail call.
1359
1360Note the difference between {{stream-find}}
1361and {{stream-any}} -- {{stream-find}} returns the element that
1362satisfied the predicate; {{stream-any}} returns the true value that the
1363predicate produced.
1364
1365Like {{stream-every}}, {{stream-any}}'s name
1366does not end with a question mark -- this is to indicate that it
1367does not return a simple boolean ({{#t}} or {{#f}}),
1368but a general value.
1369
1370<enscript highlight=scheme>(stream-any integer? (stream 'a 3 'b 2.7))
1371=> #t
1372(stream-any integer? (stream 'a 3.1 'b 2.7))
1373=> #f
1374(stream-any < (stream 3 1 4 1 5) (stream 2 7 1 8 2))
1375=> #t</enscript>
1376
1377<enscript highlight=scheme filename='stream-ext'>
1378(define (stream-any pred . strs)
1379  (and (not (find stream-null? strs))
1380       (or (apply pred (map stream-car strs))
1381           (apply stream-any pred (map stream-cdr strs)))))
1382</enscript>
1383
1384=== stream-every
1385
1386<procedure>(stream-every pred str1 str2 ...)</procedure>
1387
1388Applies the predicate across the streams,
1389returning true if the predicate returns true on every application.
1390
1391If there are {{n}} stream arguments
1392{{str1 ... strn}}, then {{pred}} must be a procedure
1393taking {{n}} arguments and returning a boolean result.
1394
1395{{stream-every}} applies {{pred}} to the first
1396elements of the {{stri}} parameters. If this application
1397returns false, {{stream-every}} immediately returns false.
1398Otherwise, it iterates, applying {{pred}} to the second
1399elements of the {{stri}} parameters, then the third, and
1400so forth. The iteration stops when a false value is produced or one
1401of the lists runs out of values. In the latter case, every returns
1402the true value produced by its final application of pred.
1403
1404Just like with {{every}} (see SRFI-1), it would be desirable
1405to make the last call to {{pred}} a tail call.  However,
1406this would force {{stream-every}} to evaluate streams in
1407advance.  For this reason, the last call to {{pred}} is
1408not a tail call.
1409
1410If one of the {{stri}}
1411has no elements, every simply returns #t.
1412
1413Like {{stream-any}}, {{stream-every}}'s
1414name does not end with a question mark -- this is to indicate
1415that it does not return a simple boolean (#t or #f), but a general value.
1416
1417<enscript highlight=scheme filename='stream-ext'>
1418(define (stream-every pred . strs)
1419  (let loop ((strs strs))
1420    (or (find stream-null? strs)
1421        (and (apply pred (map stream-car strs))
1422             (loop (map stream-cdr strs))))))
1423</enscript>
1424
1425=== stream-index
1426
1427<procedure>(stream-index pred str1 str2 ...)</procedure>
1428
1429Return the index of the leftmost elements in the
1430streams that satisfies predicate {{pred}}.
1431
1432If there are {{n}} list arguments {{str1 ... strn}},
1433then {{pred}} must be a function taking {{n}} arguments
1434and returning a boolean result.
1435
1436stream-index applies {{pred}} to the first elements of the
1437{{stri}} parameters. If this application returns true,
1438{{stream-index}} immediately returns zero. Otherwise, it
1439iterates, applying {{pred}} to the second elements of the
1440{{stri}} parameters, then the third, and so forth. When it
1441finds a tuple of list elements that cause {{pred}} to
1442return true, it stops and returns the zero-based index of that
1443position in the lists.
1444
1445The iteration stops when one of the lists runs out of values;
1446in this case, {{stream-index}} returns {{#f}}.
1447
1448<enscript highlight=scheme>(stream-index even? (stream 3 1 4 1 5 9))
1449=> 2
1450(stream-index < (stream 3 1 4 1 5 9 2 5 6) (stream 2 7 1 8 2))
1451=> 1
1452(stream-index = (stream 3 1 4 1 5 9 2 5 6) (stream 2 7 1 8 2))
1453=> #f</enscript>
1454
1455<enscript highlight=scheme filename='stream-ext'>
1456(define (stream-index pred . strs)
1457  (let loop ((strs strs) (pos 0))
1458    (and (not (find stream-null? strs))
1459         (if (apply pred (map stream-car strs))
1460             pos
1461             (loop (map stream-cdr strs) (+ pos 1))))))
1462</enscript>
1463
1464=== stream-member, stream-memq, stream-memv
1465
1466<procedure>(stream-member x str [=])</procedure>
1467<procedure>(stream-memq x str)</procedure>
1468<procedure>(stream-memv x str)</procedure>
1469
1470These procedures return the first substream of the
1471stream {{str}}
1472returned by {{(drop str i)}} for {{i}} less
1473than the length of {{str}} whose stream-car is
1474{{x}}.  If x does not occur in {{str}},
1475then either #f is returned (for finite streams) or this
1476call does not return.  {{stream-memq}} uses {{eq?}}
1477to compare x with the elements of {{str}},
1478while {{stream-memv}} uses {{eqv?}},
1479and stream-member uses {{equal?}}.
1480
1481<enscript highlight=scheme>(stream-memq 'a (stream 'a 'b 'c))
1482=> (a b c)
1483(stream-memq 'b (stream 'a 'b 'c))
1484=> (b c)
1485(stream-memq 'a (stream 'b 'c 'd))
1486=> #f
1487(stream-memq (list 'a) (stream 'b '(a) 'c))
1488=> #f
1489(stream-member (list 'a) (stream 'b '(a) 'c))
1490=> ((a) c)
1491(stream-memq 101 (stream 100 101 102))
1492=> *unspecified*
1493(stream-memv 101 (stream 100 101 102))
1494=> (101 102)</enscript>
1495
1496{{stream-member}} allows the client to pass in an optional equality procedure {{=}}
1497used to compare elements.
1498
1499The comparison procedure is used to compare the elements {{ei}}
1500of {{str}} to the element {{x}} in this way:
1501
1502<enscript highlight=scheme>(= x ei) ; str is (E1 ...)</enscript>
1503
1504That is, the first argument is always {{x}},
1505and the second argument is one of the list elements.
1506Thus one can reliably find the first element of {{str}} that
1507is greater than five with {{(stream-member 5 list <)}}.
1508
1509Note that fully general stream searching may be performed with
1510the {{stream-find-tail}} and {{stream-find}} procedures, e.g.
1511
1512<enscript highlight=scheme>; Find the first pair with an even stream-car:
1513(stream-find-tail even? str)</enscript>
1514
1515<enscript highlight=scheme filename='stream-ext'>
1516(define (stream-member-real x str =)
1517  (stream-find-tail (cut = x <>) str))
1518
1519(define (stream-member x str . rest)
1520  (stream-member-real x str (if (null? rest) equal? (car rest))))
1521
1522(define stream-memq (cut stream-member-real <...> eq?))
1523(define stream-memv (cut stream-member-real <...> eqv?))
1524</enscript>
1525
1526== Sorting
1527
1528=== stream-sort
1529
1530<procedure>(stream-sort str <)</procedure>
1531
1532Returns a copy of {{str}} with its elements sorted.
1533
1534We don't care about the slowness of converting to a list and then back to a
1535stream since
1536
1537* The entire set of elements will be needed in memory and
1538
1539* Sort has greater algorithmical complexity {{O(N) = N*log(N)}}
1540than the conversions.
1541
1542<enscript highlight=scheme filename='stream-ext'>
1543(define (stream-sort stream ord)
1544  (list->stream (sort (stream->list stream) ord)))
1545</enscript>
1546
1547== Strings as streams
1548
1549=== stream-downcase, stream-upcase
1550
1551<procedure>(stream-downcase str)</procedure>
1552<procedure>(stream-upcase str)</procedure>
1553
1554Returns a stream identical to the stream of characters {{str}} but
1555with all characters converted to lowercase or uppercase.
1556
1557<enscript highlight=scheme filename='stream-ext'>
1558(define stream-downcase (cut stream-map char-downcase <>))
1559(define stream-upcase   (cut stream-map char-upcase   <>))
1560</enscript>
1561
1562=== stream-format
1563
1564<procedure>(stream-format fmt ...)</procedure>
1565
1566Does the same as {{(format #f fmt ...)}},
1567but returns the result as a stream of characters rather than a string.
1568
1569<enscript highlight=scheme filename='stream-ext'>
1570(define (stream-format fmt . rest)
1571  (with-output-to-stream
1572    (lambda ()
1573      (format #f fmt rest))))
1574</enscript>
1575
1576=== stream-lines
1577
1578<procedure>(stream-lines str)</procedure>
1579
1580Returns a stream with the lines found in the stream of
1581characters {{str}}.  Each line is itself returned
1582as a stream of characters.  It is an error if {{str}} contains
1583elements that are not characters.
1584
1585<enscript highlight=scheme>(stream-lines (stream #\h #\e #\y #\newline #\y #\o #\u))
1586=> #<stream (#<stream (#\h #\e #\y)> #<stream (#\y #\o #\u)>)></enscript>
1587
1588<enscript highlight=scheme filename='stream-ext'>
1589(define stream-lines (cut stream-split <> (cut equal? <> #\newline)))
1590</enscript>
1591
1592=== stream-unlines
1593
1594TODO: Document
1595
1596<enscript highlight=scheme filename='stream-ext'>
1597(define (stream-unlines lines)
1598  (stream-concatenate (stream-intersperse lines (stream #\newline))))
1599</enscript>
1600
1601== Deletion
1602
1603=== stream-delete
1604
1605<procedure>(stream-delete x str [=])</procedure>
1606
1607{{stream-delete}} returns a stream identical to {{str}}
1608but removing all occurences of the element {{x}}.  The comparison
1609procedure {{=}}, which defaults to {{equal?}}, is used to
1610find them.
1611
1612The stream is not disordered -- elements that appear in the result stream
1613occur in the same order as they occur in the argument stream.
1614
1615Note that fully general element deletion can be performed with the stream-remove procedure, e.g.:
1616
1617<enscript highlight=scheme>;; Delete all the even elements from STR:
1618(stream-remove even? str)</enscript>
1619
1620The comparison procedure is used in this way: {{(= x ei)}}. That
1621is, {{x}} is always the first argument, and a element from the stream
1622is always the second argument.  Thus, one can reliably remove all the numbers
1623greater than five from a stream with {{(delete 5 stream <)}}.
1624
1625<enscript highlight=scheme filename='stream-ext'>
1626(define (stream-delete x str . rest)
1627  (stream-remove
1628    (let ((= (if (null? rest) equal? (car rest))))
1629      (lambda (elt) (= x elt)))
1630    str))
1631</enscript>
1632
1633=== stream-delete-duplicates
1634
1635<procedure>(stream-delete-duplicates str [=])</procedure>
1636
1637{{stream-delete-duplicates}} removes duplicate elements from the
1638{{str}} stream argument.  If there are multiple equal elements in the
1639argument stream, the result stream only contains the first or leftmost of these
1640elements in the result. The order of these surviving elements is the same as in
1641the original stream -- {{stream-delete-duplicates}} does not disorder
1642the stream.
1643
1644The {{=}} parameter is used to compare the elements of the list; it
1645defaults to {{equal?}}. If {{x}} comes before {{y}}
1646in list, then the comparison is performed {{(= x y)}}.  The comparison
1647procedure will be used to compare each pair of elements in list no more than
1648once; the order in which it is applied to the various pairs is not
1649specified.
1650
1651Be aware that, in general, {{stream-delete-duplicates}} runs in time O(n2) for
1652n-streams lists. Uniquifying long lists can be accomplished in O(n lg n) time
1653by sorting the stream to bring equal elements together, then using a linear-time
1654algorithm to remove equal elements. Alternatively, one can use algorithms based
1655on element-marking, with linear-time results.
1656
1657Also note that a list might be kept in memory with the entire contents
1658of the stream during the execution of calls to this function.
1659
1660<enscript highlight=scheme>(stream-delete-duplicates (stream 0 1 0 3 0 1 3 4))
1661=> #<stream (0 1 3 4)></enscript>
1662
1663<enscript highlight=scheme filename='stream-ext'>
1664(define (stream-delete-duplicates str . rest)
1665  (stream-delete-dups str '() (if (null? rest) equal? (car rest))))
1666
1667(define (stream-delete-dups str already =)
1668  (stream-delay
1669    (cond
1670      ((stream-null? str) stream-null)
1671      ((any (lambda (x) (= x (stream-car str))) already)
1672       (stream-delete-dups (stream-cdr str) already =))
1673      (else
1674        (stream-cons (stream-car str)
1675                     (stream-delete-dups (stream-cdr str) (cons (stream-car str) already) =))))))
1676</enscript>
1677
1678== Other undocumented code
1679
1680The following procedures are also provided.
1681
1682TODO: Move them to the appropriate sections in this document and get rid of this section.
1683
1684<enscript highlight=scheme filename='stream-ext'>
1685(define (stream-convert-safe check? convert)
1686  (lambda (obj)
1687    (if (check? obj)
1688      (convert obj)
1689      obj)))
1690
1691(define (stream-wrap-proc-generic convert-inputs convert-outputs)
1692  (lambda (proc)
1693    (lambda args
1694      (receive results
1695               (apply proc (map convert-inputs args))
1696        (apply values (map convert-outputs results))))))
1697
1698(define stream-wrap-proc-string
1699  (stream-wrap-proc-generic
1700    (stream-convert-safe stream? stream->string)
1701    (stream-convert-safe string? string->stream)))
1702
1703(define stream-wrap-proc-list
1704  (stream-wrap-proc-generic
1705    (stream-convert-safe stream? stream->list)
1706    (stream-convert-safe list? list->stream)))
1707
1708(define stream-wrap-proc-stream
1709  (stream-wrap-proc-generic
1710    (lambda (obj)
1711      (cond
1712        ((list? obj) (list->stream obj))
1713        ((string? obj) (string->stream obj))
1714        (else obj)))
1715    identity))
1716
1717;;; Pattern Matching
1718
1719(define (stream-grep re stream)
1720  (let ((real-re (if (string? re) (regexp re) re)))
1721    (stream-filter (cut string-match real-re <>) stream)))
1722
1723; (equal? tail stream-null) rather than (stream-null? tail) to avoid an
1724; off-by-one error (evaluating tail before obj is fully consumed).
1725
1726(define (->stream-char obj . rest)
1727  (stream-delay
1728   (let-optionals rest ((tail stream-null))
1729     (cond
1730      ((string? obj) (string->stream obj tail))
1731      ((or (number? obj) (boolean? obj) (symbol? obj)) (->stream-char (->string obj) tail))
1732      ((char? obj) (stream-cons obj tail))
1733      ((port? obj) (port->stream obj))
1734      ((stream? obj)
1735       (if (equal? tail stream-null)
1736           obj
1737           (stream-append obj tail)))
1738      (else (error "Unable to convert object to stream-char" obj))))))
1739
1740(define (stream-replace in reps)
1741  (if (stream-null? in)
1742      stream-null
1743      (let ((obj (assoc (stream-car in) reps)))
1744        (if obj
1745            (->stream-char (cadr obj) (stream-replace (stream-cdr in) reps))
1746            (stream-cons (stream-car in) (stream-replace (stream-cdr in) reps))))))
1747
1748(define (stream-translate str from to)
1749  (stream-map (lambda (c) (if (equal? c from) to c)) str))
1750</enscript>
1751
1752== Version History
1753
1754;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.
1755;1.5: Build script now uses exports.
1756;1.4.1: Small bug fix in {{stream-fold-right}}.
1757;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.
1758;1.3.1: Replaced use of {{(end-of-file)}} with {{#!eof}}
1759;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}}.
1760;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}}.
1761;1.1 : Removed {{stream-filter}} (it's provided by srfi-40).
1762;1.0 : First public release.
Note: See TracBrowser for help on using the repository browser.