Re: some suggestions

[Matthias Neubauer <neubauer@xxxxxxxxxxxxxxxxxxxxxxxxxx>]

Phil Bewig <pbewig@xxxxxxxxxx> writes:

> I think the STREAM-ITERATE in the core does exactly what
> your STREAM-UNFOLD does, and certainly your STREAM-FROM
> and STREAM-FROM-TO examples can be written based on
> STREAM-ITERATE.  And, given that STREAM is in the core, your
> LIST->STREAM can be written
> 
>     (define (list->stream lst) (apply stream lst))

You can always define a stream using STREAM-UNFOLD if a definition
involving STREAM-ITERATE is given. But the other way around isn't
feasible in general (not counting solutions using nasty side effects
of course). Here is the difference between STREAM-ITERATE and
STREAM-UNFOLD:

STREAM-ITERATE computes a subsequent element of a stream, x_{i+1},
using its previous element, x_i, as sole input to the function
FUNC. The following ascii scribble should help to illustrate this:

 x_0 -FUNC-> x_1 -FUNC-> x_2 -FUNC-> ... x_i -FUNC-> x_{i+1} ...

STREAM-UNFOLD on the other hand does not only rely on the previous
element for each computation step but it instead passes an additional
"state" s_i from step to step:

           /-> x_1      /-> x_2      /->     x_i      /-> x_{i+1}
  s_0 -FUNC--> s_1 -FUNC--> s_2 -FUNC--> ... s_i -FUNC--> s_{i+1}

The big win with the second approach is, that the passed state can be
of any type (i.e., it does not have to coincide with the type of
stream elements at all) and thus can also hold some additional
information needed to compute the next element besides the stream
elements.

Here is another example that uses this extra notion of state: Suppose
you would like to generate a stream of numbers where the difference of
to consecutive numbers always increases by one from step to step:

  1, 2, 4, 7, 11, 16, 22, ...

As you can see, you can't compute the element just by using its
predecessor. Instead you can remember for each step, what the current
distance to the following element would be. Hence, the trick is to use
STREAM-UNFOLD and put two things in the "state" passed around from
step to step---the actual element and its difference to the following
element:

(define my-stream
  (stream-unfold (lambda (state)
		   (let ((num (car state))
			 (diff (cdr state)))
		     (cons num
			   (cons  (+ num diff) (+ diff 1)))))
		 (cons 1 1)))

Another example is the definition of STREAM-FILTER. Suppose you have a
non-leaking implementation of STREAM-DROP-UNTIL at hand [1], the
following simple definition of STREAM-FILTER should (hopfully) also
make sense:

(define (stream-filter pred? stream)
  (stream-unfold (lambda (stream)
		   (let ((stream-1 (stream-drop-until pred? stream)))
		     (cons (stream-car stream-1)
			   (stream-cdr stream-1))))
		 stream))
		 
Here the "state" that is passed from step to step is the remainder of
the original stream that still has to be processed for the next
element. The actual processing in each step is then performed by
calling STREAM-DROP-UNTIL.

I won't care if you split up the srfi in two parts. And if you do so,
how. In the end, I just would like to see STREAM-UNFOLD somewhere in
the final result. At least in my experience with streams,
STREAM-UNFOLD is much more useful than many other procedures already
specified in this srfi.

-Matthias

[1] Which isn't the case with the current reference implementation I
just realized. Your STREAM-DROP-UNTIL bares the same space problems as
the naive STREAM-FILTER implementation does.

-- 
Matthias Neubauer                                       |
Universität Freiburg, Institut für Informatik           | tel +49 761 203 8060
Georges-Köhler-Allee 79, 79110 Freiburg i. Br., Germany | fax +49 761 203 8052