Hi everyone,
I'm new to the SRFI discussion, so my apologies if I do anything wrong.
SRFI-41 discusses the times3 example, noting that it should take constant
space.
But the following modified times3 example uses linear space:
(define (times3 n)
(define st
(stream-filter
(lambda (x)
(zero? (modulo x n)))
(stream-from 0)))
(stream-ref st 3)
(stream-ref st 3))
The issue, as I understand it, is that `stream-filter` holds on to the
original stream, particularly in stream-cons:
(define (stream-filter pred? strm)
(define stream-filter
(stream-lambda (strm)
(cond ((stream-null? strm) stream-null)
((pred? (stream-car strm))
(stream-cons (stream-car strm) (stream-filter (stream-cdr
strm))))
(else (stream-filter (stream-cdr strm))))))
(cond ((not (procedure? pred?)) (error 'stream-filter "non-procedural
argument"))
((not (stream? strm)) (error 'stream-filter "non-stream
argument"))
(else (stream-filter strm))))
If I'm not mistaken, one way to fix the issue is to do stream-car outside
stream-cons. This happens to be fine because stream-filter already needs to
determine the value of (pred? (stream-car strm)) before, so calling
(stream-car strm) again is fine. I call this new implementation
stream-filter*:
(define (stream-filter* pred? strm)
(define stream-filter
(stream-lambda (strm)
(cond ((stream-null? strm) stream-null)
((pred? (stream-car strm))
(let ((v (stream-car strm)))
(stream-cons v (stream-filter (stream-cdr strm)))))
(else (stream-filter (stream-cdr strm))))))
(cond ((not (procedure? pred?)) (error 'stream-filter "non-procedural
argument"))
((not (stream? strm)) (error 'stream-filter "non-stream
argument"))
(else (stream-filter strm))))
But the same pitfall applies to other operations, like stream-map, too.
Unlike stream-filter, there is no reason to force the car of a stream
early. That is to say, I don't expect anything to be displayed in the
following program:
(define st (stream-cons (begin (display "a") 1) stream-null))
(define st* (stream-map (lambda (x) (+ x 1)) st))
(stream-cdr st*)
which is unfortunate, because it means the strategy for stream-filter can't
be applied to stream-map.
One possibility to really fix this issue is to provide stream-force and a
new operation stream-car*, which is just like stream-car, but does not
stream-force the resulting value.
(define (stream-car* strm)
(cond ((not (stream? strm)) (error 'stream-car* "non-stream"))
((stream-null? strm) (error 'stream-car* "null stream"))
(else (stream-kar (stream-force strm)))))
Then the new implementation, which I call stream-map*, can be implemented
as follows:
(define (stream-map* proc . strms)
(define stream-map
(stream-lambda (strms)
(if (exists stream-null? strms)
stream-null
(let ((cars (map stream-car* strms)))
(stream-cons (apply proc (map stream-force cars))
(stream-map (map stream-cdr strms)))))))
(cond ((not (procedure? proc)) (error 'stream-map "non-procedural
argument"))
((null? strms) (error 'stream-map "no stream arguments"))
((exists (lambda (x) (not (stream? x))) strms)
(error 'stream-map "non-stream argument"))
(else (stream-map strms))))
Does this sound right?
Best,
Sorawee (Oak)
