Debian Codegraph @

lib/util/stream.scm

raw
1 ;;;
2 ;;; util.stream - stream library (SRFI-40, 41 & more)
3 ;;;
4 ;;; [SK] This module includes code from streams-ext.scm,
5 ;;; written by Alejandro Forero Cuervo and released in Public Domain
6 ;;;
7 ;;; The rest is written by Shiro Kawai
8 ;;;
9 ;;; Copyright (c) 2019-2024 Shiro Kawai <[email protected]>
10 ;;;
11 ;;; Redistribution and use in source and binary forms, with or without
12 ;;; modification, are permitted provided that the following conditions
13 ;;; are met:
14 ;;;
15 ;;; 1. Redistributions of source code must retain the above copyright
16 ;;; notice, this list of conditions and the following disclaimer.
17 ;;;
18 ;;; 2. Redistributions in binary form must reproduce the above copyright
19 ;;; notice, this list of conditions and the following disclaimer in the
20 ;;; documentation and/or other materials provided with the distribution.
21 ;;;
22 ;;; 3. Neither the name of the authors nor the names of its contributors
23 ;;; may be used to endorse or promote products derived from this
24 ;;; software without specific prior written permission.
25 ;;;
26 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
27 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
28 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
29 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
30 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
31 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
32 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 ;;;
38
39 (define-module util.stream
40 (use scheme.list)
41 (use util.match)
42 (export
43 ;; SRFI-40
44 stream? stream-null stream-cons stream-null?
45 stream-pair? stream-car stream-cdr stream-delay stream
46 stream-unfoldn stream-map stream-for-each stream-filter
47
48 ;; SRFI-41 additions
49 stream+ stream-lambda define-stream stream-unfold stream-unfolds
50 list->stream port->stream stream->list stream-append stream-concat
51 stream-constant stream-drop-while stream-take-while
52 stream-range stream-fold stream-from stream-iterate
53 stream-length stream-ref stream-reverse stream-scan stream-zip
54 stream-match stream-of stream-let
55
56 ;; extras
57 generator->stream stream-concatenate
58
59 stream-xcons stream-cons* make-stream stream-tabulate
60 stream-iota stream-format stream-lines
61 string->stream stream->string
62 number->stream stream->number symbol->stream stream->symbol
63 iterator->stream
64 stream= stream-prefix=
65 stream-caar stream-cadr stream-cdar stream-cddr
66 stream-caaar stream-caadr stream-cadar stream-caddr
67 stream-cdaar stream-cdadr stream-cddar stream-cdddr
68 stream-caaaar stream-caaadr stream-caadar stream-caaddr
69 stream-cadaar stream-cadadr stream-caddar stream-cadddr
70 stream-cdaaar stream-cdaadr stream-cdadar stream-cdaddr
71 stream-cddaar stream-cddadr stream-cdddar stream-cddddr
72 stream-first stream-second stream-third stream-fourth
73 stream-fifth stream-sixth stream-seventh stream-eighth
74 stream-ninth stream-tenth
75 stream-take-safe stream-take stream-drop-safe stream-drop
76 stream-intersperse stream-split stream-last stream-last-n
77 stream-butlast stream-butlast-n stream-length>= stream-length=
78 stream-count
79 stream-remove stream-partition stream-find stream-find-tail
80 stream-span stream-break
81 stream-any stream-every stream-index
82 stream-member stream-memq stream-memv
83 stream-delete stream-delete-duplicates
84 stream-grep ->stream-char stream-replace stream-translate
85 write-stream
86 ))
87 (select-module util.stream)
88
89 ;;;
90 ;;; <stream> type is a promise with 'stream in its kind.
91 ;;;
92
93 (define-inline (stream? s)
94 (and (promise? s) (eq? (promise-kind s) 'stream)))
95
96 (define-inline (%make-stream promise)
97 (set! (promise-kind promise) 'stream)
98 promise)
99
100 ;;;
101 ;;; Primitives
102 ;;;
103
104 ;; SRFI-40, 41
105 ;; A singleton instance of null stream
106 (define stream-null (%make-stream (delay '())))
107
108 ;; SRFI-40, 41
109 (define-syntax stream-cons
110 (syntax-rules ()
111 [(stream-cons obj strm)
112 (%make-stream (delay (cons obj strm)))]))
113
114 ;; SRFI-40, 41
115 (define-inline (stream-null? obj)
116 (and (stream? obj) (null? (force obj))))
117 (define-inline (stream-pair? obj)
118 (and (stream? obj) (pair? (force obj))))
119 (define-inline (stream-car s) (car (force s)))
120 (define-inline (stream-cdr s) (cdr (force s)))
121
122 ;; SRFI-40
123 (define-syntax stream-delay
124 (syntax-rules ()
125 [(stream-delay expr)
126 (%make-stream (lazy expr))]))
127
128 ;; SRFI-41
129 (define-syntax stream-lambda
130 (syntax-rules ()
131 [(_ formals body0 body1 ...)
132 (lambda formals (stream-delay (let () body0 body1 ...)))]))
133
134 ;;;
135 ;;; Derived
136 ;;;
137
138 ;; SRFI-40 (objs are evaluated first)
139 (define (stream . objs)
140 (if (null? objs)
141 stream-null
142 (stream-cons (car objs) (apply stream (cdr objs)))))
143
144 ;; SRFI-41's stream (evaluation of objs are delayed)
145 (define-syntax stream+
146 (syntax-rules ()
147 [(_) stream-null]
148 [(_ x y ...) (stream-cons x (stream+ y ...))]))
149
150 ;; SRFI-41
151 (define-syntax define-stream
152 (syntax-rules ()
153 [(_ (name . formal) body0 body1 ...)
154 (define name (stream-lambda formal body0 body1 ...))]))
155
156 ;; SRFI-41
157 ;; NB: The argument order differs from srfi.1#unfold. Also, predicate is
158 ;; to continue, as oppsed to the stop predicate in srfi.1#unfold.
159 (define-stream (stream-unfold f p g seed)
160 (if (p seed)
161 (stream-cons (f seed) (stream-unfold f p g (g seed)))
162 stream-null))
163
164 ;; SRFI-40
165 (define (stream-unfoldn f seed n)
166 ;; stream of N-tuples of the results
167 (define rstream
168 ((rec (loop seed)
169 (stream-delay
170 (receive (seed . rs) (f seed)
171 (stream-cons rs (loop seed)))))
172 seed))
173 ;; create N-th stream
174 (define (nth-stream rss i)
175 (stream-delay
176 (let1 r (~ (stream-car rss) i)
177 (cond [(pair? r) (stream-cons (car r) (nth-stream (stream-cdr rss) i))]
178 [(not r) (nth-stream (stream-cdr rss) i)]
179 [else stream-null]))))
180 (apply values (map (cute nth-stream rstream <>) (iota n))))
181
182 ;; SRFI-41
183 ;; Similar to stream-unfoldn, but the number of result streams is inferred
184 ;; from the number of returned values from f.
185 (define (stream-unfolds f seed)
186 (receive vs (f seed)
187 (stream-unfoldn f seed (- (length vs) 1))))
188
189 ;; SRFI-40, 41
190 (define (stream-map f s . ss)
191 (if (null? ss)
192 (let loop [(s s)]
193 (stream-delay
194 (if (stream-null? s)
195 s
196 (stream-cons (f (stream-car s)) (loop (stream-cdr s))))))
197 (let loop ([ss (cons s ss)])
198 (stream-delay
199 (if (any stream-null? ss)
200 stream-null
201 (stream-cons (apply f (map stream-car ss))
202 (loop (map stream-cdr ss))))))))
203
204 ;; SRFI-40, 41
205 (define (stream-for-each f s . ss)
206 (if (null? ss)
207 (let loop [(s s)]
208 (unless (stream-null? s)
209 (f (stream-car s))
210 (loop (stream-cdr s))))
211 (let loop [(ss (cons s ss))]
212 (unless (any stream-null? ss)
213 (apply f (map stream-car ss))
214 (loop (map stream-cdr ss))))))
215
216 ;; SRFI-40, 41
217 (define-stream (stream-filter p s)
218 (cond [(stream-null? s) s]
219 [(p (stream-car s)) (stream-cons (stream-car s)
220 (stream-filter p (stream-cdr s)))]
221 [else (stream-filter p (stream-cdr s))]))
222
223 ;; SRFI-41
224 (define (list->stream lis)
225 (stream-unfold car pair? cdr lis))
226
227 (define (generator->stream gen :optional (fini #f))
228 ((rec (next)
229 (stream-delay
230 (let1 v (gen)
231 (cond [(eof-object? v)
232 (when fini (fini))
233 stream-null]
234 [else (stream-cons v (next))]))))))
235
236 ;; SRFI-41
237 ;; reader and close-at-eof are Gauche extension.
238 (define (port->stream :optional (in (current-input-port))
239 (reader read-char)
240 (close-at-eof #f))
241 (generator->stream (cut reader in)
242 (^[] (when close-at-eof (close-at-eof in)))))
243
244 ;; SRFI-41
245 (define stream->list
246 (case-lambda
247 [(n s)
248 (assume n <integer>)
249 (assume (stream? s))
250 (let loop ([n n] [s s] [r '()])
251 (cond [(<= n 0) (reverse r)]
252 [(stream-null? s) (reverse r)]
253 [else (loop (- n 1) (stream-cdr s) (cons (stream-car s) r))]))]
254 [(s)
255 (assume (stream? s))
256 (let loop ([s s] [r '()])
257 (if (stream-null? s)
258 (reverse r)
259 (loop (stream-cdr s) (cons (stream-car s) r))))]))
260
261 ;; SRFI-41
262 (define (stream-append . ss)
263 (stream-delay
264 (cond [(null? ss) stream-null]
265 [(null? (cdr ss)) (car ss)]
266 [else
267 (let loop ([s (car ss)] [ss (cdr ss)])
268 (stream-delay
269 (if (stream-null? s)
270 (apply stream-append ss)
271 (stream-cons (stream-car s) (loop (stream-cdr s) ss)))))])))
272
273 ;; SRFI-41
274 (define (stream-concat ss)
275 (stream-delay
276 (if (stream-null? ss)
277 stream-null
278 (stream-append (stream-car ss)
279 (stream-concat (stream-cdr ss))))))
280
281 ;; for the backward compatibility
282 (define stream-concatenate stream-concat)
283
284 ;; SRFI-41
285 (define (stream-constant . objs)
286 (list->stream (apply circular-list objs)))
287
288 ;; SRFI-41
289 (define-stream (stream-drop-while pred s)
290 (if (or (stream-null? s) (not (pred (stream-car s))))
291 s
292 (stream-drop-while pred (stream-cdr s))))
293
294 ;; SRFI-41
295 (define-stream (stream-take-while pred s)
296 (if (or (stream-null? s) (not (pred (stream-car s))))
297 stream-null
298 (stream-cons (stream-car s)
299 (stream-take-while pred (stream-cdr s)))))
300
301 ;; SRFI-41
302 (define (stream-fold f seed s)
303 (let loop ([seed seed] [s s])
304 (if (stream-null? s)
305 seed
306 (loop (f seed (stream-car s)) (stream-cdr s)))))
307
308 ;; SRFI-41
309 (define (stream-from start :optional (step 1))
310 (stream-range start +inf.0 step))
311
312 ;; SRFI-41
313 ;; NB: End being optional is Gauche's extension
314 (define (stream-range start :optional (end +inf.0) step)
315 (assume real? start)
316 (assume real? end)
317 (let* ([step (if (undefined? step)
318 (if (<= start end) 1 -1)
319 (begin (assume real? step) step))]
320 [cmp (if (negative? step) > <)])
321 (if (and (exact? start)
322 (or (exact? end) (infinite? end))
323 (exact? step))
324 (let loop ((start start))
325 (stream-delay
326 (if (cmp start end)
327 (stream-cons start (loop (+ start step)))
328 stream-null)))
329 (let loop ((k 0))
330 (stream-delay
331 (let1 v (+. start (* k step))
332 (if (cmp v end)
333 (stream-cons v (loop (+ k 1)))
334 stream-null)))))))
335
336 ;; SRFI-41
337 (define-stream (stream-iterate proc base)
338 (stream-cons base (stream-iterate proc (proc base))))
339
340 ;; SRFI-41
341 (define (stream-length s)
342 (let loop ([n 0] [s s])
343 (if (stream-null? s) n (loop (+ n 1) (stream-cdr s)))))
344
345 ;; SRFI-41
346 (define-syntax stream-let
347 (syntax-rules ()
348 [(_ tag ((var expr) ...) body0 body1 ...)
349 ((letrec ((tag (stream-lambda (var ...) body0 body1 ...))) tag)
350 expr ...)]))
351
352 ;; SRFI-41
353 (define (stream-ref s n)
354 (if (zero? n)
355 (stream-car s)
356 (stream-ref (stream-cdr s) (- n 1))))
357
358 ;; SRFI-41
359 (define (stream-reverse s)
360 (stream-fold stream-xcons stream-null s))
361
362 ;; SRFI-41
363 (define-stream (stream-scan f seed s)
364 (if (stream-null? s)
365 (stream-cons seed stream-null)
366 (stream-cons seed
367 (stream-scan f (f seed (stream-car s)) (stream-cdr s)))))
368
369 ;; SRFI-41
370 (define (stream-zip . ss)
371 (define-stream (rec ss)
372 (if (any stream-null? ss)
373 stream-null
374 (stream-cons (map stream-car ss) (rec (map stream-cdr ss)))))
375 (rec ss))
376
377 ;;;
378 ;;; SRFI-41 matcher
379 ;;;
380
381 (define-syntax stream-match
382 (er-macro-transformer
383 (^[f r c]
384 ;; returns length of normal patvars, and flag of rest var
385 (define (patlen pat)
386 (let loop ([pat pat] [n 0])
387 (cond [(null? pat) (values n #f)]
388 [(pair? pat) (loop (cdr pat) (+ n 1))]
389 [(identifier? pat) (values n #t)]
390 [else (errorf "Bad pattern element ~s in stream-match: ~s" f)])))
391 (define (flatpat pat)
392 (map* identity (^t (if (null? t) '() (list t))) pat))
393 ;; produce one cond clause
394 (define (expand-clause s clause)
395 (match clause
396 [(pat expr)
397 (receive (n rest?) (patlen pat)
398 (if rest?
399 (quasirename r
400 `[(stream-length>= ,s ,n)
401 (apply (lambda ,(flatpat pat) ,expr)
402 (stream->list+stream ,s ,n))])
403 (quasirename r
404 `[(stream-length= ,s ,n)
405 (apply (lambda ,pat ,expr) (stream->list ,n ,s))])))]
406 [(pat fender expr)
407 (receive (n rest?) (patlen pat)
408 (if rest?
409 (quasirename r
410 `[(and-let* ([ (stream-length>= ,s ,n) ]
411 [args (stream->list+stream ,s ,n)]
412 [ (apply (lambda ,(flatpat pat) ,fender) args) ])
413 args)
414 => (cut apply (lambda ,(flatpat pat) ,expr) <>)])
415 (quasirename r
416 `[(and-let* ([ (stream-length= ,s ,n) ]
417 [args (stream->list ,n ,s)]
418 [ (apply (lambda ,par ,fender) args) ])
419 args)
420 => (cut apply (lambda ,pat ,expr) <>)])))]
421 [_ (error "invalid clause ~s in stream-match: ~s" clause f)]))
422
423 (match f
424 [(_ stream clause ...)
425 (when (null? clause)
426 (error "malformed stream-match: no clauses:" f))
427 (quasirename r
428 `(let1 s ,stream
429 (cond ,@(map (cut expand-clause (r's) <>) clause))))]
430 [_ (error "malformed stream-match:" f)]))))
431
432 ;; Aux fn for stream-match
433 ;; {a b c d e ...} => (a b c {d e ...}) etc.
434 ;; assume we alreadh check s has more than n elts.
435 (define (stream->list+stream s n)
436 (if (= n 0)
437 (list s)
438 (cons (stream-car s) (stream->list+stream (stream-cdr s) (- n 1)))))
439
440 ;;;
441 ;;; SRFI-41 comprehension
442 ;;;
443
444 ;; The following 'stream-of' definition is taken from SRFI-41 reference
445 ;; implementation. This kind of code is where syntax-rules shines.
446 ;;
447 ;; Copyright (C) Philip L. Bewig (2007). All Rights Reserved.
448 ;;
449 ;; Permission is hereby granted, free of charge, to any person obtaining
450 ;; a copy of this software and associated documentation
451 ;; files (the "Software"), to deal in the Software without restriction,
452 ;; including without limitation the rights to use, copy, modify, merge,
453 ;; publish, distribute, sublicense, and/or sell copies of the Software,
454 ;; and to permit persons to whom the Software is furnished to do so,
455 ;; subject to the following conditions:
456 ;;
457 ;; The above copyright notice and this permission notice shall be
458 ;; included in all copies or substantial portions of the Software.
459
460 (define-syntax stream-of
461 (syntax-rules ()
462 ((_ expr rest ...)
463 (stream-of-aux expr stream-null rest ...))))
464
465 (define-syntax stream-of-aux
466 (syntax-rules (in is)
467 ((stream-of-aux expr base)
468 (stream-cons expr base))
469 ((stream-of-aux expr base (var in stream) rest ...)
470 (stream-let loop ((strm stream))
471 (if (stream-null? strm)
472 base
473 (let ((var (stream-car strm)))
474 (stream-of-aux expr (loop (stream-cdr strm)) rest ...)))))
475 ((stream-of-aux expr base (var is exp) rest ...)
476 (let ((var exp)) (stream-of-aux expr base rest ...)))
477 ((stream-of-aux expr base pred? rest ...)
478 (if pred? (stream-of-aux expr base rest ...) base))))
479
480 ;; End of excerpt from SRFI-41 reference implementation
481
482 ;;;
483 ;;; Extras
484 ;;;
485
486 ;; The following procedures are taken from stream-ext.scm by
487 ;; Alejandro Forero Cuervo <[email protected]>
488
489 ;; Constructors
490 (define (stream-xcons a b) (stream-cons b a))
491
492 (define-stream (stream-cons* . elts)
493 (if (null? (cdr elts))
494 (car elts)
495 (stream-cons (car elts) (apply stream-cons* (cdr elts)))))
496
497 (define (make-stream n . rest)
498 (stream-tabulate n (if (null? rest)
499 (^_ #f)
500 (^_ (car rest)))))
501
502 (define (stream-tabulate n init-proc)
503 (stream-let loop ((i 0))
504 (if (equal? i n)
505 stream-null
506 (stream-cons (init-proc i) (loop (+ i 1))))))
507
508 (define (stream-iota :optional (count +inf.0) (start 0) (step 1))
509 (define cnt (if (< count 0) +inf.0 count)) ;; for the backward compatibility
510 (if (and (or (exact? cnt) (infinite? cnt))
511 (exact? start)
512 (exact? step))
513 (let loop ([c cnt] [s start])
514 (stream-delay
515 (if (<= c 0)
516 stream-null
517 (stream-cons s (loop (- c 1) (+ s step))))))
518 (let loop ([k 0])
519 (stream-delay
520 (if (>= k cnt)
521 stream-null
522 (stream-cons (+. start (* k step)) (loop (+ k 1))))))))
523
524 (define (stream-format fmt . rest)
525 (string->stream (apply format fmt rest)))
526
527 (define stream-lines (cut stream-split <> (cut equal? <> #\newline)))
528
529 ;; Conversion
530
531 (define (string->stream str :optional (tail stream-null))
532 (let loop ((i 0))
533 (stream-delay
534 (if (equal? i (string-length str))
535 tail
536 (stream-cons (string-ref str i) (loop (+ i 1)))))))
537
538 (define stream->string (compose list->string stream->list))
539 (define number->stream (compose string->stream number->string))
540 (define stream->number (compose string->number stream->string))
541 (define stream->symbol (compose string->symbol stream->string))
542 (define symbol->stream (compose string->stream symbol->string))
543
544
545
546 ;(define (make-output-port-char write close)
547 ; (make-output-port
548 ; (lambda (string)
549 ; (let loop ((i 0))
550 ; (when (< i (string-length string))
551 ; (write (string-ref string i))
552 ; (loop (+ i 1)))))
553 ; close))
554
555 (define (iterator->stream proc)
556 (stream-delay
557 (call-with-current-continuation
558 (lambda (return)
559 (proc
560 (lambda (obj)
561 (call-with-current-continuation
562 (lambda (next)
563 (return
564 (stream-cons obj
565 (stream-delay
566 (call-with-current-continuation
567 (lambda (new)
568 (set! return new)
569 (next #t)))))))))
570 (lambda () (return stream-null)))
571 (return stream-null)))))
572
573 ;(define (with-output-to-stream proc)
574 ; (iterator->stream
575 ; (lambda (write close)
576 ; (with-output-to-port
577 ; (make-output-port
578 ; (lambda (string)
579 ; (let loop ((i 0))
580 ; (when (< i (string-length string))
581 ; (write (string-ref string i))
582 ; (loop (+ i 1)))))
583 ; close)
584 ; proc))))
585
586 ;(define (with-input-from-stream stream proc)
587 ; (with-input-from-port
588 ; (make-input-port
589 ; (lambda ()
590 ; (if (stream-null? stream)
591 ; (end-of-file)
592 ; (let ((char (stream-car stream)))
593 ; (set! stream (stream-cdr stream))
594 ; char)))
595 ; (lambda ()
596 ; (not (stream-null? stream)))
597 ; (lambda ()
598 ; (set! stream stream-null))
599 ; (lambda ()
600 ; (stream-car stream)))
601 ; proc))
602
603 ;; Predicates
604
605 (define (stream= elt= . strs)
606 (or (every stream-null? strs)
607 (and (not (any stream-null? strs))
608 (let loop ((es (map stream-car strs)))
609 (or (null? (cdr es))
610 (and (elt= (car es) (cadr es)) (loop (cdr es)))))
611 (apply stream= elt= (map stream-cdr strs)))))
612
613 (define (stream-prefix= str prefix . rest)
614 (if (null? prefix)
615 str
616 (and (not (stream-null? str))
617 ((if (null? rest) equal? (car rest)) (stream-car str) (car prefix))
618 (apply stream-prefix= (stream-cdr str) (cdr prefix) rest))))
619
620 ;; Selectors
621
622 (define (stream-caar x) (stream-car (stream-car x)))
623 (define (stream-cadr x) (stream-car (stream-cdr x)))
624 (define (stream-cdar x) (stream-cdr (stream-car x)))
625 (define (stream-cddr x) (stream-cdr (stream-cdr x)))
626
627 (define (stream-caaar x) (stream-caar (stream-car x)))
628 (define (stream-caadr x) (stream-caar (stream-cdr x)))
629 (define (stream-cadar x) (stream-cadr (stream-car x)))
630 (define (stream-caddr x) (stream-cadr (stream-cdr x)))
631 (define (stream-cdaar x) (stream-cdar (stream-car x)))
632 (define (stream-cdadr x) (stream-cdar (stream-cdr x)))
633 (define (stream-cddar x) (stream-cddr (stream-car x)))
634 (define (stream-cdddr x) (stream-cddr (stream-cdr x)))
635
636 (define (stream-caaaar x) (stream-caaar (stream-car x)))
637 (define (stream-caaadr x) (stream-caaar (stream-cdr x)))
638 (define (stream-caadar x) (stream-caadr (stream-car x)))
639 (define (stream-caaddr x) (stream-caadr (stream-cdr x)))
640 (define (stream-cadaar x) (stream-cadar (stream-car x)))
641 (define (stream-cadadr x) (stream-cadar (stream-cdr x)))
642 (define (stream-caddar x) (stream-caddr (stream-car x)))
643 (define (stream-cadddr x) (stream-caddr (stream-cdr x)))
644 (define (stream-cdaaar x) (stream-cdaar (stream-car x)))
645 (define (stream-cdaadr x) (stream-cdaar (stream-cdr x)))
646 (define (stream-cdadar x) (stream-cdadr (stream-car x)))
647 (define (stream-cdaddr x) (stream-cdadr (stream-cdr x)))
648 (define (stream-cddaar x) (stream-cddar (stream-car x)))
649 (define (stream-cddadr x) (stream-cddar (stream-cdr x)))
650 (define (stream-cdddar x) (stream-cdddr (stream-car x)))
651 (define (stream-cddddr x) (stream-cdddr (stream-cdr x)))
652
653 (define stream-first stream-car)
654 (define stream-second stream-cadr)
655 (define stream-third stream-caddr)
656 (define stream-fourth stream-cadddr)
657 (define (stream-fifth x) (stream-car (stream-cddddr x)))
658 (define (stream-sixth x) (stream-cadr (stream-cddddr x)))
659 (define (stream-seventh x) (stream-caddr (stream-cddddr x)))
660 (define (stream-eighth x) (stream-cadddr (stream-cddddr x)))
661 (define (stream-ninth x) (stream-car (stream-cddddr (stream-cddddr x))))
662 (define (stream-tenth x) (stream-cadr (stream-cddddr (stream-cddddr x))))
663
664 (define (stream-take-safe stream count)
665 (stream-delay
666 (if (or (zero? count) (stream-null? stream))
667 stream-null
668 (stream-cons (stream-car stream)
669 (stream-take-safe (stream-cdr stream) (- count 1))))))
670
671 (define (stream-drop-safe str count)
672 (stream-delay
673 (if (or (zero? count) (stream-null? str))
674 str
675 (stream-drop-safe (stream-cdr str) (- count 1)))))
676
677 ;; NB: SRFI-41 has arguments reversed
678 (define (stream-take stream count)
679 (stream-delay
680 (if (zero? count)
681 stream-null
682 (stream-cons (stream-car stream)
683 (stream-take (stream-cdr stream) (- count 1))))))
684
685 ;; NB: SRFI-41 has arguments reversed
686 (define (stream-drop str count)
687 (stream-delay
688 (if (zero? count)
689 str
690 (stream-drop (stream-cdr str) (- count 1)))))
691
692 (define (stream-intersperse stream element)
693 (stream-delay
694 (if (stream-null? stream)
695 stream-null
696 (stream-cons (stream-car stream)
697 (let loop ((rest (stream-cdr stream)))
698 (if (stream-null? rest)
699 stream-null
700 (stream-cons element
701 (stream-cons (stream-car rest)
702 (loop (stream-cdr rest))))))))))
703
704 (define (stream-split in p?)
705 (let loop ((current '()) (s in))
706 (stream-delay
707 (cond
708 ((stream-null? s)
709 (if (null? current)
710 stream-null
711 (stream-cons (list->stream (reverse current)) stream-null)))
712 ((p? (stream-car s))
713 (stream-cons (list->stream (reverse current)) (loop '() (stream-cdr s))))
714 (else (loop (cons (stream-car s) current) (stream-cdr s)))))))
715
716 (define (stream-last str)
717 (if (stream-null? (stream-cdr str))
718 (stream-car str)
719 (stream-last (stream-cdr str))))
720
721 (define (stream-last-n str count)
722 (stream-delay
723 (let ((l (list #f)))
724 (set-cdr! l l)
725 (let loop ((s str) (l l) (i 0))
726 (cond
727 ((stream-null? s)
728 (if (< i count)
729 str
730 (stream-take (list->stream (cdr l)) i)))
731 ((equal? i count)
732 (set-car! l (stream-car s))
733 (loop (stream-cdr s) (cdr l) i))
734 (else
735 (set-car! l (stream-car s))
736 (set-cdr! l (cons i (cdr l)))
737 (loop (stream-cdr s) (cdr l) (+ i 1))))))))
738
739 (define (stream-butlast str)
740 (stream-butlast-n str 1))
741
742 (define (stream-butlast-n str count)
743 (stream-delay
744 (let loop ((head str) (tail (stream-drop str count)))
745 (if (stream-null? tail)
746 stream-null
747 (stream-cons (stream-car head)
748 (loop (stream-cdr head) (stream-cdr tail)))))))
749
750 ;; Miscelaneous: length, append, concatenate, reverse, zip & count
751
752 (define (stream-length>= s len)
753 (or (zero? len)
754 (and (not (stream-null? s))
755 (stream-length>= (stream-cdr s) (- len 1)))))
756
757 (define (stream-length= s len)
758 (if (zero? len)
759 (stream-null? s)
760 (stream-length= (stream-cdr s) (- len 1))))
761
762 (define (stream-concatenate strs)
763 (stream-delay
764 (if (stream-null? strs)
765 stream-null
766 (stream-append (stream-car strs)
767 (stream-concatenate (stream-cdr strs))))))
768
769 (define (stream-count pred . strs)
770 (let loop ((times 0) (s strs))
771 (if (any stream-null? s)
772 times
773 (loop (+ times (if (apply pred (map stream-car s)) 1 0))
774 (map stream-cdr s)))))
775
776 ;; Filtering & Partitioning
777
778 (define (stream-remove pred str)
779 (stream-filter (complement pred) str))
780
781 ; The following version is faster than the current but has the problem of
782 ; eagerly evaluating the streams rather than create them as they are
783 ; needed (so, for instance, it won't work in infinite streams).
784
785 ;(define (stream-partition pred str)
786 ; (if (stream-null? str)
787 ; (values stream-null stream-null)
788 ; (receive (in out) (stream-partition pred (stream-cdr str))
789 ; (if (pred (stream-car str))
790 ; (values (stream-cons (stream-car str) in) out)
791 ; (values in (stream-cons (stream-car str) out))))))
792
793 (define (stream-partition pred str)
794 (values (stream-filter pred str)
795 (stream-remove pred str)))
796
797 ;; Searching
798
799 (define (stream-find pred str)
800 (let ((result (stream-find-tail pred str)))
801 (and result (stream-car result))))
802
803 (define (stream-find-tail pred str)
804 (and (not (stream-null? str))
805 (if (pred (stream-car str))
806 str
807 (stream-find-tail pred (stream-cdr str)))))
808
809 (define (stream-span pred str)
810 (values (stream-take-while pred str) (stream-drop-while pred str)))
811
812 (define (stream-break pred str)
813 (stream-span (^x (not (pred x))) str))
814
815 (define (stream-any pred . strs)
816 (and (not (find stream-null? strs))
817 (or (apply pred (map stream-car strs))
818 (apply stream-any pred (map stream-cdr strs)))))
819
820 (define (stream-every pred . strs)
821 (or (any stream-null? strs)
822 (let loop ([strs strs])
823 (cond [(apply pred (map stream-car strs))
824 => (^r (let1 cdrs (map stream-cdr strs)
825 (if (any stream-null? cdrs)
826 r
827 (loop cdrs))))]
828 [else #f]))))
829
830 (define (stream-index pred . strs)
831 (let loop ((strs strs) (pos 0))
832 (and (not (find stream-null? strs))
833 (if (apply pred (map stream-car strs))
834 pos
835 (loop (map stream-cdr strs) (+ pos 1))))))
836
837 (define (stream-member-real x str =)
838 (stream-find-tail (lambda (elt) (= x elt)) str))
839
840 (define (stream-member x str . rest)
841 (stream-member-real x str (if (null? rest) equal? (car rest))))
842
843 (define (stream-memq x str) (stream-member-real x str eq?))
844 (define (stream-memv x str) (stream-member-real x str eqv?))
845
846 ;; Deletion
847
848 (define (stream-delete x str . rest)
849 (stream-remove
850 (let ((= (if (null? rest) equal? (car rest))))
851 (lambda (elt) (= x elt)))
852 str))
853
854 (define (stream-delete-duplicates str . rest)
855 (stream-delete-dups str '() (if (null? rest) equal? (car rest))))
856
857 (define (stream-delete-dups str already =)
858 (stream-delay
859 (cond
860 ((stream-null? str) stream-null)
861 ((any (^x (= x (stream-car str))) already)
862 (stream-delete-dups (stream-cdr str) already =))
863 (else
864 (stream-cons (stream-car str)
865 (stream-delete-dups (stream-cdr str) (cons (stream-car str) already) =))))))
866
867 ;; Pattern Matching
868
869 (define (stream-grep re stream)
870 (let ((real-re (if (string? re) (string->regexp re) re)))
871 (stream-filter (cut real-re <>) stream)))
872
873 ; (equal? tail stream-null) rather than (stream-null? tail) to avoid an
874 ; off-by-one error (evaluating tail before obj is fully consumed).
875
876 (define (->stream-char obj :optional (tail stream-null))
877 (stream-delay
878 (cond
879 ((string? obj) (string->stream obj tail))
880 ((or (number? obj) (boolean? obj) (symbol? obj)) (->stream-char (x->string obj) tail))
881 ((char? obj) (stream-cons obj tail))
882 ((port? obj) (port->stream obj))
883 ((stream? obj)
884 (if (equal? tail stream-null)
885 obj
886 (stream-append obj tail)))
887 (else (error "Unable to convert object to stream-char" obj)))))
888
889 (define (stream-replace in reps)
890 (if (stream-null? in)
891 stream-null
892 (let ((obj (assoc (stream-car in) reps)))
893 (if obj
894 (->stream-char (cadr obj) (stream-replace (stream-cdr in) reps))
895 (stream-cons (stream-car in) (stream-replace (stream-cdr in) reps))))))
896
897 (define (stream-translate str from to)
898 (stream-map (^c (if (equal? c from) to c)) str))
899
900 (define (write-stream stream :optional
901 (port (current-output-port)) (writer write-char))
902 (let loop ((s stream))
903 (unless (stream-null? s)
904 (writer (stream-car s) port)
905 (loop (stream-cdr s)))))
906
907 ;(define (stream-chomp stream . args)
908 ; (stream-delay
909 ; (let-optionals args ((lastchar #\newline))
910 ; (if (or (stream-null? stream)
911 ; (and (stream-null? (stream-cdr stream))
912 ; (char=? lastchar (stream-car stream))))
913 ; stream-null
914 ; (stream-cons (stream-car stream) (stream-chomp (stream-cdr stream) lastchar))))))