Lazy lists - an implementation.

[Richard Carlsson]

On Tue, 17 Oct 2000, Sean Hinde wrote:

> > And here is my first version of a lazy lists library. Seems 
> > to work ok.
> 
> Just so I (and I guess others?) understand how all this would be
> applied to the original problem (that iterating over very large lists
> causes large heaps to be generated)..
> 
> If we already have a large list and want to generate another I guess
> there would there be no benefit of converting this into a lazy_list
> first? (would this make a Huge fun?)

Not "Huge" - the function "lazy(L)" takes your normal list and embeds it
in a small fun (no copying done) which will on demand return the next
element. The space usage is comparable to a tuple with a small number of
elements.

> If we already have the list and want to do say a checksum calc on it
> (foreach/2) there is no advantage because we still have to run through
> all the elements (ok, one at a time)?

Yes.

> So this could be used where the list itself doesn't already exist and
> we want to iterate to produce a result which isn't a list? Wouldn't
> the stack then fill up with the not yet calculated results of each
> iteration?

Well, what the result is (list or not) is not important as such, and an
iteration like the following executes in constant space:

	sum(L) -> sum(L, 0).
	sum(L, A) ->
	    case L() of
	        [H | T] -> sum(T, A + H);
	        [] -> A
	    end.

What happens is that the "lazy list" will never really be built in memory
as a list - the producer just uses cons cells to pass the next element on
demand (the "tail" is the function to use for getting the element after
that, and so forth), and [] to signal "the end".

> My head is starting to spin. Under what circumstances would this stuff
> be very appropriate to use?

For one thing, if you were to have a "final consumer" of some list (or
"stream"), which would take elements one at a time and use them for
something, bluntly assuming that they are right for its task, and you have
some producer that has passed you a lazy list (stream), and you want to
apply some modification to the elements (map, filter, merge, ...) - but
you don't want to read the whole list, do your thing to it, and send the
result to the consumer - you just want to "attach" the modification
without requesting a single element before the consumer decides that it
wants one. Using a lazy list:

	transmogrify(L) ->
	    L1 = lazy_lists:map(fun my_filter/1, L),
	    consumer(L1).

Now, the "map" will be applied to each element as the consumer requests
them, and not until then. You can in this way attach any sort of
complicated modification to a lazy list (stream) without having to pass
callback hooks to the consumer through a complicated interface. You just
pass your new lazy list.

	/Richard



Richard Carlsson (richardc@REDACTED)   (This space intentionally left blank.)
E-mail: Richard.Carlsson@REDACTED	WWW: http://www.csd.uu.se/~richardc/