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

[oleg@xxxxxxxxx: Re: M:N Dictionaries and lazy fold enumerator]



----- Forwarded message from oleg@xxxxxxxxx -----
>On laziness of collection-fold-left

Andre van Tonder wrote:

> You state that for an infinite collection, *-fold-left is only haltable
> via the folding function.  This seems to presuppose that *-fold-left
> is strict, and not itself lazy, as, for example, in SRFI-40 (where the
> result of folding over a stream is another stream).  Since it is often
> the lazy semantics that is desired for streams, I think this should be
> clarified.   

> But them I could not use this SRFI for lazy collections.  


I'm afraid there is some confusion over terminology. Could it be that
the similarity of *-fold-left with foldl in Haskell is confusing?

In Haskell (and in general), foldl is strict: it does not yield an
answer until it sees the end of a collection. OTH, foldr is
non-strict: when the user-supplied function returns without evaluating
its right argument, the iteration is finished. But
collection-fold-left has a premature termination feature: a
user-supplied function can decide when to stop iterating. At that
point, the enumerator yields the answer. Therefore, *-fold-left can be
said to have the termination behavior of foldr but the order of
foldl. *-fold-left can be used as it is for infinite and lazy
collections. It's up to the implementor to decide how much to evaluate
ahead, if at all. But the interface supports lazy collections without
any changes. You may wish to read a short discussion on the Haskell
mailing list about file enumerators with premature termination. I can
showed that the enumerator does not read from the file more than it
needs.

> This seems to presuppose that *-fold-left
> is strict, and not itself lazy, as, for example, in SRFI-40 (where the
> result of folding over a stream is another stream).

The enumerator inversion algorithm gives you a lazy list (a stream)
for _any_ *-fold-left enumerator (over finite, infinite, or lazy
collection).

It appears then no changes to the SRFI-44 document is necessary. Or
this point has to be clarified in the document?



----- End forwarded message -----

Attachment: pgpfbU1rxbWlS.pgp
Description: PGP signature