[plt-scheme] how do you use stream-partition?

From: Jos Koot (jos.koot at telefonica.net)
Date: Sat Mar 15 12:40:47 EDT 2008

As you may have noticed there are some redundant stream-delays in my 
stream-partition. However, the general idea should be clear: 
stream-partition must produce two interdependent streams, for clearly it is 
the intention that the predicate is applied once only for each element of 
the original stream. Otherwise we could simply use (stream-filter odd? 
stream) for the odd stream and (stream-filter even? stream) for the even 
stream. This means that a force of the even stream may affect the odd 
stream, and reversely. They MUST affect each other in order to prevent the 
predicate from being called superfluously. Therefore both streams must have 
state that can can be modified by both. The state is contained in box a and 
variable stream for the even stream and box b and variable stream for the 
other stream. It is very tricky to combine imperative things like set! and 
set-box! with lazy evaluation. You have to make sure that the side effects 
are effectuated in the right order. I checked my version of stream-partition 
not to call the predicate twice for the same element of the original stream 
and to produce the side effects in the right order. The relationship between 
imperative side effects and lazy evaluation is one of my fascinations.
Jos


----- Original Message ----- 
From: "Jos Koot" <jos.koot at telefonica.net>
To: "Doug Orleans" <dougorleans at gmail.com>; "PLT-Scheme Mailing List" 
<plt-scheme at list.cs.brown.edu>
Sent: Saturday, March 15, 2008 3:53 PM
Subject: Re: [plt-scheme] how do you use stream-partition?


> The following stream-partition works, I think.
>
> (define (stream-partition pred stream)
> (define a (box stream-null)) ; satisfying pred
> (define b (box stream-null)) ; not satisfying pred
> (define (get-a) (partition pred a b))
> (define (get-b) (partition (lambda (x) (not (pred x))) b a))
> (define (partition pred a b)
>  (stream-delay
>   (if (stream-null? (unbox a))
>    (if (stream-null? stream) stream-null
>     (let ([x (stream-car stream)])
>      (set! stream (stream-cdr stream))
>      (cond
>       ((pred x)
>        (stream-cons x (partition pred a b)))
>       (else
>        (set-box! b (stream-append (unbox b) (stream-cons x stream-null)))
>        (partition pred a b)))))
>    (let ((x (stream-car (unbox a))))
>     (set-box! a (stream-cdr (unbox a)))
>     (stream-cons x (stream-delay (partition pred a b)))))))
> (values (stream-delay (get-a)) (stream-delay (get-b))))
>
> Jos
>
> ----- Original Message ----- 
> From: "Doug Orleans" <dougorleans at gmail.com>
> To: "PLT-Scheme Mailing List" <plt-scheme at list.cs.brown.edu>
> Sent: Saturday, March 15, 2008 12:40 AM
> Subject: [plt-scheme] how do you use stream-partition?
>
>
>>I want to use stream-partition from dherman's stream.plt, which uses
>> SRFI-40 streams, but I can't figure out what to do with the result:
>>
>>  Welcome to MzScheme v3.99.0.10 [3m], Copyright (c) 2004-2008 PLT Scheme 
>> Inc.
>>  Reading .mzschemerc...
>>  > (require srfi/40)
>>  > (define (integers-starting-from n)
>>      (stream-cons n (integers-starting-from (+ n 1))))
>>  > (require (planet "stream.ss" ("dherman" "stream.plt" 1 0)))
>>  > (stream->list (stream-take 5 (integers-starting-from 0)))
>>  (0 1 2 3 4)
>>  > (define-values (evens odds)
>>      (stream-partition even? (integers-starting-from 0)))
>>  define-values: context (defining "evens", ...) expected 2 values, 
>> received 1 value: #<stream>
>>
>>   === context ===
>>  /usr/local/plt/collects/scheme/private/misc.ss:63:7
>>
>>  > (stream? (stream-partition even? (integers-starting-from 0)))
>>  #t
>>  > (stream-pair? (stream-partition even? (integers-starting-from 0)))
>>  context (lexical binding) expected 2 values, received 1 value: #<stream>
>>
>>   === context ===
>>  /usr/local/plt/collects/srfi/40/stream.ss:82:2: stream-pair?
>>  /usr/local/plt/collects/scheme/private/misc.ss:63:7
>>
>> Neither module provides a stream-force, and all the stream functions
>> expect a delayed single value, so what can I do with this stream?
>>
>> --dougorleans at gmail.com
>> _________________________________________________
>>  For list-related administrative tasks:
>>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme 



Posted on the users mailing list.