Re: [boost] Lazy list

Subject: Re: [boost] Lazy list
From: Sebastian Redl (sebastian.redl_at_[hidden])
Date: 2009-01-18 07:14:26

Zachary Turner wrote:
> Has this been considered before, and can anyone think of any technical
> limitations that would prevent such a class to be written?
>   
Lazy lists typically rely on a garbage collector to clean up nodes that
aren't used anymore. You can achieve the same effect with
reference-counting pointers to each node, but the overhead would be
significant.

The second problem with the implementation is state. It's rather tricky
to correctly keep state in such a list, especially if you want to allow
discarding and re-evaluating older list nodes. This requires that the
function in question returns a tuple (next value, next function), which
makes the overhead grow further and is really unidiomatic to program in C++.

Also, lazy lists are really an idiom from languages that are very
comfortable with lists, i.e. mostly functional languages (Haskell, for
example). The same idiom is, I believe, really not as practical in C++
and other imperative languages. Modern C++ uses iterator ranges as the
primary concept for generic handling of finite and infinite sequences,
and there already are function-backed input iterators. The second
concept used is input streams.

Do you have a motivating use case for such lists?

Sebastian