source: project/wiki/stream-ext @ 12671

Last change on this file since 12671 was 12671, checked in by azul, 13 years ago

Updating version history.

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