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

Re: stream-partition is not incremental

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: 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)))))