On Mon, Jan 19, 2009 at 1:11 PM, OvermindDL1 <overminddl1@gmail.com> 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.