Lazy lists - an implementation.
Wed Oct 18 13:09:25 CEST 2000
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
> 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)?
> 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
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
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:
L1 = lazy_lists:map(fun my_filter/1, L),
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 Carlsson () (This space intentionally left blank.)
E-mail: WWW: http://www.csd.uu.se/~richardc/
More information about the erlang-questions