[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Stream-filter and space leaks

This page is part of the web mail archives of SRFI 40 from before July 7th, 2015. The new archives for SRFI 40 contain all messages, not just those from before July 7th, 2015.



   From: Phil Bewig <pbewig@xxxxxxxxxx>
   Date: Fri, 21 Feb 2003 10:57:22 +0100

   Your STREAM-UNFOLDN and STREAM-FILTERN look interesting, though I'd
   be interested to know how often they would actually be useful.

They are useful any time you want to produce new streams from
existing ones without getting a space leak.  You'll never be
able to add every possible stream function to the SRFI.  You
can instead try to make it easy for people to write new ones
on their own.  Having STREAM-UNFOLDN (which could use a better
name) is one way of doing so.  I would much rather have one good
general-purpose function than ZIP, UNZIP, ALTERNATE, INTERLEAVE,
MERGE, and so on.  

For example, suppose I want to use a stream of integers to index
into a list of other streams.  The following is a bit ugly, but
it shouldn't have any space leaks if STREAM-UNFOLDN doesn't.
(This code hasn't been tested because I haven't written
STREAM-UNFOLDN.)

; Returns a stream created by using INDEX-STREAM to pick which of
; INDEXED-STREAM provides the next element.

(define (stream-index index-stream indexed-streams)
  (stream-unfoldn
   (lambda (streams)
     (let ((index-stream (car streams))
	   (indexed-streams (cdr streams)))
       (if (stream-null? index-stream)
	   (values (list index-stream)		; no longer need the rest
		   '())				; output stream is done
	   (call-with-values
	    (lambda ()
	      (indexed-force (stream-car index-stream) indexed-streams))
	    (lambda (next indexed-streams)
	      (values (cons index-stream indexed-streams)	; next seed
		      (list next))))				; next result
   (cons index-stream indexed-streams)	         ; initial seed
   1))						 ; one resulting stream

; Returns two values: the STREAM-CAR of the I'th stream and a copy of STREAMS
; with the I'th element replaced by its own STREAM-CDR.     

(define (indexed-force i streams)
  (do ((i i (- i 1))
       (unseed streams (cdr unseen))
       (seen '() (cons (car unseen) seen)))
      ((= i 0)
       (values (stream-car (car unseen))
	       (append (reverse seen)
		       (cons (stream-cdr (car unseen))
			     (cdr unseen)))))))

This uses a slightly different version of STREAM-UNFOLDN.  Now that
I have actually tried to use it this seems cleaner.

   (stream-unfoldn generator seed n) -> n streams
   
STREAM-UNFOLDN returns N streams whose contents are produced by
successive calls to GENERATOR, which takes the current seed as
an arguments and returns N + 1 values:
    (proc seed) -> seed result0 ... resultN
where resultI contains indicates how to produce the next element
of the Ith result stream:  
     (value)  -> value is the next CAR of this result stream
     #f       -> no new information for this result stream
     ()       -> the end of this result stream has been reached
Note that getting the next element in any particular result stream
may require multiple calls to GENERATOR.

                                        -Richard