It occured to me that boost is lacking a true lazy list. I feel like this should be possible to implement on most compilers, although I doubt I have the metaprogramming expertise to be able to implement such a data structure myself. But nonetheless I think this would be extremely useful. Lazy lists are basically lists that don't store the actual values of the list, instead they store a -function- that is called each time the next element of the list is requested, and the result of that list is returned. Most likely there is a caching mechanism as well, so that accessing recently accessed (or preceding) elements would return a cached value if it had already been accessed. I guess it would not cache arbitrarily large amounts of elements though for memory usage reasons, otherwise it would defeat the whole purpose, which is the ability to expose truly infinite sequences to the user in the form of a list. Has this been considered before, and can anyone think of any technical limitations that would prevent such a class to be written?
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
On Sun, Jan 18, 2009 at 8:14 PM, Sebastian Redl <sebastian.redl@getdesigned.at> wrote: [snip]
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.
There are already function-backed input iterators in Boost? I know there are function-backed output iterators, but not function-backed input iterators. I myself have been looking for something in Boost that would invoke a function when an iterator is dereferenced and the result of which would be a value. There are two types that I'm thinking of: a forward iterator that invoked a nullary function and returned the result, and a random access iterator that forwarded the base+offset to the stored function. Is there interest in these two types? -- Dean Michael C. Berris Software Engineer, Friendster, Inc.
on Sun Jan 18 2009, "Dean Michael Berris" <mikhailberis-AT-gmail.com> wrote:
On Sun, Jan 18, 2009 at 8:14 PM, Sebastian Redl <sebastian.redl@getdesigned.at> wrote: [snip]
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.
There are already function-backed input iterators in Boost?
I know there are function-backed output iterators, but not function-backed input iterators.
http://www.boost.org/doc/libs/1_37_0/libs/utility/generator_iterator.htm -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Mon, Jan 19, 2009 at 3:17 AM, David Abrahams <dave@boostpro.com> wrote:
on Sun Jan 18 2009, "Dean Michael Berris" <mikhailberis-AT-gmail.com> wrote:
There are already function-backed input iterators in Boost?
I know there are function-backed output iterators, but not function-backed input iterators.
http://www.boost.org/doc/libs/1_37_0/libs/utility/generator_iterator.htm
Oh my. I kept looking in Boost.Iterators and I didn't see this one. This is news to me. Shouldn't this be in Boost.Iterators ? Because if I was looking for a function-backed iterator I would have looked in Boost.Iterators -- and judging from where it's located, it doesn't make sense to me that it's in "Utility". -- Dean Michael C. Berris Software Engineer, Friendster, Inc.
Shouldn't this be in Boost.Iterators ? Because if I was looking for a function-backed iterator I would have looked in Boost.Iterators -- and judging from where it's located, it doesn't make sense to me that it's in "Utility".
I'll second that. I was looking for this kind of iterator a while ago and couldn't find it - I tried to make a counting_iterator instead but wasn't happy with it so I gave up in the end. ~Alex
On Mon, 19 Jan 2009 13:07:53 +0800, "Dean Michael Berris" <mikhailberis@gmail.com> wrote:
On Mon, Jan 19, 2009 at 3:17 AM, David Abrahams <dave@boostpro.com> wrote:
on Sun Jan 18 2009, "Dean Michael Berris" <mikhailberis-AT-gmail.com> wrote:
There are already function-backed input iterators in Boost?
I know there are function-backed output iterators, but not function-backed input iterators.
http://www.boost.org/doc/libs/1_37_0/libs/utility/generator_iterator.htm
Oh my. I kept looking in Boost.Iterators and I didn't see this one.
This is news to me.
Shouldn't this be in Boost.Iterators ? Because if I was looking for a function-backed iterator I would have looked in Boost.Iterators -- and judging from where it's located, it doesn't make sense to me that it's in "Utility".
Yes, you're probably right -- David Abrahams Boostpro Computing http://www.boostpro.com
On Mon, Jan 19, 2009 at 04:18, David Abrahams <dave@boostpro.com> wrote:
On Mon, 19 Jan 2009 13:07:53 +0800, "Dean Michael Berris" <mikhailberis@gmail.com> wrote:
On Mon, Jan 19, 2009 at 3:17 AM, David Abrahams <dave@boostpro.com>
wrote:
http://www.boost.org/doc/libs/1_37_0/libs/utility/generator_iterator.htm
Shouldn't this be in Boost.Iterators ? Because if I was looking for a function-backed iterator I would have looked in Boost.Iterators -- and judging from where it's located, it doesn't make sense to me that it's in "Utility".
Yes, you're probably right
If people are moving iterators around, perhaps they could consider moving http://spirit.sourceforge.net/distrib/spirit_1_8_5/libs/spirit/doc/multi_pas... as well -- I didn't find that until after I had written my own.
On Mon, Jan 19, 2009 at 8:35 AM, Scott McMurray <me22.ca+boost@gmail.com> wrote:
On Mon, Jan 19, 2009 at 04:18, David Abrahams <dave@boostpro.com> wrote:
On Mon, 19 Jan 2009 13:07:53 +0800, "Dean Michael Berris" <mikhailberis@gmail.com> wrote:
On Mon, Jan 19, 2009 at 3:17 AM, David Abrahams <dave@boostpro.com>
wrote:
http://www.boost.org/doc/libs/1_37_0/libs/utility/generator_iterator.htm
Shouldn't this be in Boost.Iterators ? Because if I was looking for a function-backed iterator I would have looked in Boost.Iterators -- and judging from where it's located, it doesn't make sense to me that it's in "Utility".
Yes, you're probably right
If people are moving iterators around, perhaps they could consider moving http://spirit.sourceforge.net/distrib/spirit_1_8_5/libs/spirit/doc/multi_pas... as well -- I didn't find that until after I had written my own. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
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.
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.
Zachary Turner wrote:
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
This cannot be very efficient, nor very safe. As I said earlier, foreach(int i, make_range(1, 1) | append_rec(_1 + _2) | limit(100)) std::cout << i << std::endl; seems like a much better design to me. Actually, I've done that for some time already. This is obviously a Boost.RangeEx extension. append_rec() takes an N-ary function object and returns an adaptor that takes a range of at least N elements and returns an infinite range that applies the function object recursively. This can check at compile-time that the range has enough elements, for example. Also, it can reuse any other existing range, including one defined like this. No need for caching: the adaptor can memorize the previous N elements of a given position.
On Sun, Jan 18, 2009 at 6:14 AM, Sebastian Redl < sebastian.redl@getdesigned.at> wrote:
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?
Do you have a motivating use case for such lists?
Sebastian
I don't have an immediate need for one if that's what you mean, but in the past when I have done programming in functional languages I have always found them extraordinarily useful and would find uses for them even when I wasn't really expecting to. These days, however, I do much less mathematical / scientific programming which is where they tend to find most of their applications. While it is not exactly a practical usage, one of the easiest-to-describe problems that lazy lists provide a particularly elegant solution to is ascending order generation of hamming numbers. I'm not quite sure I agree though that it's simply a functional "idiom". I think it's a general programming idiom, that just so happens to be easier to implement in functional languages. But even Mpl has started to adopt certain aspects of lazy evaluation. I think lazy lists can allow elegant and expressive specification and description of problems that can otherwise be quite difficult to express without them, regardless of language. But of course if it really isn't practical to implement in C++ then I can just scratch the idea :)
Zachary Turner wrote:
I'm not quite sure I agree though that it's simply a functional "idiom". I think it's a general programming idiom, that just so happens to be easier to implement in functional languages. But even Mpl has started to adopt certain aspects of lazy evaluation.
MPL is a library for template metaprogramming, and the template meta-language is functional. Sebastian
Zachary Turner wrote:
It occured to me that boost is lacking a true lazy list. I feel like this should be possible to implement on most compilers, although I doubt I have the metaprogramming expertise to be able to implement such a data structure myself. But nonetheless I think this would be extremely useful. Lazy lists are basically lists that don't store the actual values of the list, instead they store a -function- that is called each time the next element of the list is requested, and the result of that list is returned.
Such things could easily be done with range adaptors. auto fibo = make_range(0, 1) | append_rec(_1 + _2); This could generate the infinite fibonacci range.
participants (8)
-
Alex MDC -
David Abrahams -
Dean Michael Berris -
Mathias Gaunard -
OvermindDL1 -
Scott McMurray -
Sebastian Redl -
Zachary Turner