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

Re: stream-partition is not incremental

> From: Stephen McCracken <samccpa@xxxxxxxxx>

> The reference implementation of stream-partition
> appears to evaluate the entire stream before returning
> any results.  As such, it has no advantages over a
> function that operates on lists.

> ;; Obvious quick fix:  This tests each element twice, 
> ;; and it may have problems with space retention.
> (define (stream-partition pred? strm)
>   (values 
>     (stream-filter pred? strm)
>     (stream-filter (lambda (x) (not (pred? x)))
>                    strm)))

> It might be possible to write a stream-partition that
> was incremental but still tested each element only
> once.

Here's one untested way to do so:

  (define (stream-partition pred? strm)

    ;; Filter2 returns a stream of all the elements of stream VALS for
    ;; which the corresponding element of stream BOOLS is not #f.
    (define (filter2 vals bools)
      (cond ((stream-null? vals) stream-null)
	    ((stream-car bools)
	     (stream-cons (stream-car vals)
			  (filter2 (stream-cdr vals) (stream-cdr bools))))
	    (else (filter2 (stream-cdr vals) (stream-cdr bools)))))

    (let ((bools (stream-map pred? strm)))
      (values (filter2 strm bools)
	      (filter2 strm (stream-map not bools)))))