Re: [boost] Lazy list

Subject: Re: [boost] Lazy list
From: Zachary Turner (divisortheory_at_[hidden])
Date: 2009-01-19 14:57:42

On Mon, Jan 19, 2009 at 1:11 PM, OvermindDL1 <overminddl1_at_[hidden]> wrote:

> Just out of curiosity, but it sounds as if to me that your lazy list
> is essentially just a function that returns a value for a given
> argument, so why not just call a function, passing in the 'index' and
> get the returned value to emulate a random-access list, or why not
> just use a struct to keep state with its operator() always returning
> the next value to emulate the forward-access list, you could even have
> both of them as structs anyway and have them fullfill the iterator
> pattern too, such as using the above libraries in boost.  If any
> caching is wanted it could easily be done by a static in a function or
> as a member variable in a struct.
>

Well for starters what data type is the index?  Is it a uint32?  If so then
what if I pass in an index larger than 2^32?  Likewise, for any data type T,
what happens if I need to access the element at index n, where n is greater
than the largest value that T can represent?  You could create some custom
big_int class that can represent arbitrarily large integers, but this is
obviously not ideal.  The main motivation behind lazy lists is to be able to
present literally infinite sequences to the user as an actual sequence.

function backed iterators are "close", I wasn't aware of there existence
like a few other people in the thread I guess, and while that's probably
what I'll use instead of a lazy list whenever the need arises again, they
still lack some of the same elegance, in particular the caching and the
ability to have different functions for different elements (am I wrong about
this with function-backed iterators?)  With a lazy list you can even specify
a recursive function as your accessor which is particularly useful.  You can
probably find a way to make function back iterators work with this concept
as well, where instead of returning the value directly from the "get"
function, you return the value, as well as the function to compute the next
value.  I can imagine the code for this might be messy.  Imagine if, using
boost labmda expressions, I could write:

lazylist<int> fib;
fib.push_back(1);
fib.push_back(1);
fib.push_back(_1->prev + _1->prev->prev);

foreach(fib.begin(), fib.iter(100), cout << _1);   //print the first 100
fibonacci numbers

That would be the definition of sexy (well, my definition of sexy anyway)
;-)

As someone pointed out earlier in the thread, caching is one of the biggest
problems due to the lack of garbage collection.  After some more thought I
think I agree that particular issue would probably prevent it from being as
useful as lazy lists in functional languages.  There are cases where if n is
a positive integer and f_n is the function to compute the n'th value given
the previous n-1 values, that as n approaches infinity not only does the
number of previous values required by f_n in order to perform the
computation approach infinity, but also the number of _successive_ values
that end up being computed by the function also approaches infinity.  I
guess there's no easy way to handle this efficiently without garbage
collection.