function based associative generator
Hi Everyone, I've recently been playing around with a relatively simple idea: creating a generic associative generator. For some background, here's a simple problem (which is quite common in mathematics): I want to be able to pull out the nth fibonacci number in the fibonacci sequence. To do this, the traditional implementation in C++ would be to create a function that yields the nth fibonacci number. This seems fine, because as C++ programmers we would be used to the notion of using functions. However, the traditional notion of a sequence in mathematics is a collection of values that can be indexed by a subscript. Consider: struct fibonacci { int operator () (int n) const { // ... }; }; boost::generator<int, int> const & fib = boost::generator<int, int>(fibonacci()); std::cout << fib[1] << std::endl; // prints 1st fibonacci number std::cout << fib[2] << std::endl; // prints 2nd fibonacci number ... Now consider that you want to deal with the generator using an STL algorithm: std::copy(fib.begin(), fib.end(), ostream_iterator<int>(std::cout, " ")); // prints the infinite sequence The iterator implementation requires that the InputType (in this case, the second 'int' template parameter to the generator) be default constructable and has a defined prefix and/or postfix increment operator. The iterator models an InputIterator. Given this, I've attached the implementation which I'm opening up for comments. If there is interest in this utility, I'm willing to write documentation and submit it for a formal review. The basic idea for this utility is to map a non-void unary function to a generator interface that provides an associative index operator (operator[]) which passes the sole argument as the argument to the wrapped function. This utility requires only the Boost.Function library, and has been tested with MSVC 2008 Express Edition. Have a good one, and I hope this helps! -- Dean Michael C. Berris Software Engineer, Friendster, Inc.
Dean Michael Berris wrote:
Hi Everyone,
I've recently been playing around with a relatively simple idea: creating a generic associative generator.
For some background, here's a simple problem (which is quite common in mathematics):
I want to be able to pull out the nth fibonacci number in the fibonacci sequence. To do this, the traditional implementation in C++ would be to create a function that yields the nth fibonacci number. This seems fine, because as C++ programmers we would be used to the notion of using functions. However, the traditional notion of a sequence in mathematics is a collection of values that can be indexed by a subscript. Consider:
struct fibonacci { int operator () (int n) const { // ... }; };
boost::generator<int, int> const & fib = boost::generator<int, int>(fibonacci()); std::cout << fib[1] << std::endl; // prints 1st fibonacci number std::cout << fib[2] << std::endl; // prints 2nd fibonacci number ...
Now consider that you want to deal with the generator using an STL algorithm:
std::copy(fib.begin(), fib.end(), ostream_iterator<int>(std::cout, " ")); // prints the infinite sequence
If you're using Binet's formula, that's a pretty inefficient way to compute all those Fibs, isn't it? Or does your generator cache nearby Fibs?
The iterator implementation requires that the InputType (in this case, the second 'int' template parameter to the generator) be default constructable and has a defined prefix and/or postfix increment operator. The iterator models an InputIterator.
Given this, I've attached the implementation which I'm opening up for comments.
Interesting; a const_iterator that can't be incremented ;-)
If there is interest in this utility, I'm willing to write documentation and submit it for a formal review.
The basic idea for this utility is to map a non-void unary function to a generator interface that provides an associative index operator (operator[]) which passes the sole argument as the argument to the wrapped function. This utility requires only the Boost.Function library, and has been tested with MSVC 2008 Express Edition.
Is this basically make_transform_iterator( make_counting_iterator( start ), f ) or is there more to it? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Tue, Jun 24, 2008 at 4:02 AM, David Abrahams <dave@boostpro.com> wrote:
Dean Michael Berris wrote:
Hi Everyone,
I've recently been playing around with a relatively simple idea: creating a generic associative generator.
For some background, here's a simple problem (which is quite common in mathematics):
I want to be able to pull out the nth fibonacci number in the fibonacci sequence. To do this, the traditional implementation in C++ would be to create a function that yields the nth fibonacci number. This seems fine, because as C++ programmers we would be used to the notion of using functions. However, the traditional notion of a sequence in mathematics is a collection of values that can be indexed by a subscript. Consider:
struct fibonacci { int operator () (int n) const { // ... }; };
boost::generator<int, int> const & fib = boost::generator<int, int>(fibonacci()); std::cout << fib[1] << std::endl; // prints 1st fibonacci number std::cout << fib[2] << std::endl; // prints 2nd fibonacci number ...
Now consider that you want to deal with the generator using an STL algorithm:
std::copy(fib.begin(), fib.end(), ostream_iterator<int>(std::cout, " ")); // prints the infinite sequence
If you're using Binet's formula, that's a pretty inefficient way to compute all those Fibs, isn't it? Or does your generator cache nearby Fibs?
Actually, the function object can be as stateful or state-less as you want. There's an iterative way of computing the nth fibonacci number, but that's really beside the point here. ;-)
The iterator implementation requires that the InputType (in this case, the second 'int' template parameter to the generator) be default constructable and has a defined prefix and/or postfix increment operator. The iterator models an InputIterator.
Given this, I've attached the implementation which I'm opening up for comments.
Interesting; a const_iterator that can't be incremented ;-)
Eep. I didn't have a test for that. Let me see what I can do about that. :D
If there is interest in this utility, I'm willing to write documentation and submit it for a formal review.
The basic idea for this utility is to map a non-void unary function to a generator interface that provides an associative index operator (operator[]) which passes the sole argument as the argument to the wrapped function. This utility requires only the Boost.Function library, and has been tested with MSVC 2008 Express Edition.
Is this basically
make_transform_iterator( make_counting_iterator( start ), f )
or is there more to it?
The make_*_iterator family works fine, but the problem becomes one of semantics/readability. If you just wanted iterators, the above would be sufficient. For 'prettier' syntax that models the sequence generators that other programming languages have (think Haskell's list comprehensions/construction) making something look like a list may be important. The idea really is to abstract the function that generates the list from the list it generates (lazily?) itself. Instead of doing: fib(n); Something that looks like fib[n]; May look more semantically correct. The generator can then abstract certain details from the 'accessing site' as to things like whether it's a container that actually contains things or a function that returns values. Consider for example an adjacency matrix where the adjacent vertex lists were distributed accross network resources which you can access by wrapping an accessor client in a generator<>, and access through the index operator []... Maybe that would make the code more readable doing: adjacency_matrix[n]; Instead of maybe something like: get_adjacent_vertices(n); Of course, others may have other ideas as to what other things may be done with this but the basic idea is the same -- make your function look like a sequence generator and use the 'sequence' like a real container. :-) HTH -- Dean Michael C. Berris Software Engineer, Friendster, Inc.
Dean Michael Berris wrote:
On Tue, Jun 24, 2008 at 4:02 AM, David Abrahams <dave@boostpro.com> wrote:
Dean Michael Berris wrote:
Hi Everyone,
I've recently been playing around with a relatively simple idea: creating a generic associative generator.
For some background, here's a simple problem (which is quite common in mathematics):
I want to be able to pull out the nth fibonacci number in the fibonacci sequence. To do this, the traditional implementation in C++ would be to create a function that yields the nth fibonacci number. This seems fine, because as C++ programmers we would be used to the notion of using functions. However, the traditional notion of a sequence in mathematics is a collection of values that can be indexed by a subscript. Consider:
struct fibonacci { int operator () (int n) const { // ... }; };
boost::generator<int, int> const & fib = boost::generator<int, int>(fibonacci()); std::cout << fib[1] << std::endl; // prints 1st fibonacci number std::cout << fib[2] << std::endl; // prints 2nd fibonacci number ...
Now consider that you want to deal with the generator using an STL algorithm:
std::copy(fib.begin(), fib.end(), ostream_iterator<int>(std::cout, " ")); // prints the infinite sequence If you're using Binet's formula, that's a pretty inefficient way to compute all those Fibs, isn't it? Or does your generator cache nearby Fibs?
Actually, the function object can be as stateful or state-less as you want. There's an iterative way of computing the nth fibonacci number,
Well of course; that's the easy way to do it... but it makes random access with fib[n] very inefficient.
but that's really beside the point here. ;-)
Well, _my_ point was to find out whether your proposal was going to figure out how to handle both random access and sequential iteration efficiently. Sounds like it isn't.
If there is interest in this utility, I'm willing to write documentation and submit it for a formal review.
The basic idea for this utility is to map a non-void unary function to a generator interface that provides an associative index operator (operator[]) which passes the sole argument as the argument to the wrapped function. This utility requires only the Boost.Function library, and has been tested with MSVC 2008 Express Edition. Is this basically
make_transform_iterator( make_counting_iterator( start ), f )
or is there more to it?
The make_*_iterator family works fine, but the problem becomes one of semantics/readability. If you just wanted iterators, the above would be sufficient. For 'prettier' syntax that models the sequence generators that other programming languages have (think Haskell's list comprehensions/construction) making something look like a list may be important.
The idea really is to abstract the function that generates the list from the list it generates (lazily?) itself. Instead of doing:
fib(n);
Something that looks like
fib[n];
May look more semantically correct.
But... you can already use operator[] on a random access iterator. So if you're not going to explicitly solve the problem of efficient sequential and random-access traversals, boost::transform_iterator< boost::counting_iterator<T>, boost::function<T(T)>
already does what you want, I think.
The generator can then abstract certain details from the 'accessing site' as to things like whether it's a container that actually contains things or a function that returns values. Consider for example an adjacency matrix where the adjacent vertex lists were distributed accross network resources which you can access by wrapping an accessor client in a generator<>, and access through the index operator []... Maybe that would make the code more readable doing:
adjacency_matrix[n];
Instead of maybe something like:
get_adjacent_vertices(n);
Of course, others may have other ideas as to what other things may be done with this but the basic idea is the same -- make your function look like a sequence generator and use the 'sequence' like a real container. :-)
So far this doesn't seem to have much of substance that isn't already in the iterators library, but I could be missing something. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Tue, Jun 24, 2008 at 2:22 PM, David Abrahams <dave@boostpro.com> wrote:
Dean Michael Berris wrote:
On Tue, Jun 24, 2008 at 4:02 AM, David Abrahams <dave@boostpro.com> wrote:
std::copy(fib.begin(), fib.end(), ostream_iterator<int>(std::cout, " ")); // prints the infinite sequence
If you're using Binet's formula, that's a pretty inefficient way to compute all those Fibs, isn't it? Or does your generator cache nearby Fibs?
Actually, the function object can be as stateful or state-less as you want. There's an iterative way of computing the nth fibonacci number,
Well of course; that's the easy way to do it... but it makes random access with fib[n] very inefficient.
The inefficiency is actually inherent in the underlying function implementation, and not directly as an effect of using the generator to wrap the function.
but that's really beside the point here. ;-)
Well, _my_ point was to find out whether your proposal was going to figure out how to handle both random access and sequential iteration efficiently. Sounds like it isn't.
Accessing the generator wouldn't be inefficient whether you access it using operator[] or sequentially. Unless you're thinking that somehow the generator will cache results of previously accessed data and encapsulate an appropriately random-accessible container (like an std::vector) to mitigate the recomputation of already previously accessed data; would this be something that would be considered a value-add for a general-purpose utility?
The make_*_iterator family works fine, but the problem becomes one of semantics/readability. If you just wanted iterators, the above would be sufficient. For 'prettier' syntax that models the sequence generators that other programming languages have (think Haskell's list comprehensions/construction) making something look like a list may be important.
The idea really is to abstract the function that generates the list from the list it generates (lazily?) itself. Instead of doing:
fib(n);
Something that looks like
fib[n];
May look more semantically correct.
But... you can already use operator[] on a random access iterator. So if you're not going to explicitly solve the problem of efficient sequential and random-access traversals,
boost::transform_iterator< boost::counting_iterator<T>, boost::function<T(T)>
already does what you want, I think.
Almost does it, but not necessarily. Constructing an instance of the transform iterator would require the instantiation of the counting_iterator as well. template <class ResultType, class InputType> struct generator { typedef transform_iterator< function<ResultType(InputType)>, counting_iterator<InputType>
iterator; typedef iterator const const_iterator;
iterator begin() { return make_transform_iterator( counting_iterator<InputType>(), _function ); }; const_iterator begin() const { return make_transform_iterator( counting_iterator<InputType>(), _function ); }; iterator end() { return iterator(); }; const_iterator end() const { return const_iterator(); }; generator() : _function() { }; generator(function<ResultType(InputType)> const & f) : _function(f) { }; ResultType operator[](InputType i) const { return _function(i); }; private: mutable function<ResultType(InputType)> _function; }; The generator now adapts the function provided into a 'pseudo-container' of sorts which provides you with a means of indexing elements in the 'container' using the index operator. However, I suppose that it's a matter of convenience really whether or not to use a transform_iterator instead of the provided utility above. Looking at the counting_iterator documentation, I suppose the generator wrapper provides non-void unary functions an index operator and begin()+end() iterators to make it look like an infinite* lazily generated random-access container. * - well of course, the bounds would be dependent on the valid range of values of InputType.
The generator can then abstract certain details from the 'accessing site' as to things like whether it's a container that actually contains things or a function that returns values. Consider for example an adjacency matrix where the adjacent vertex lists were distributed accross network resources which you can access by wrapping an accessor client in a generator<>, and access through the index operator []... Maybe that would make the code more readable doing:
adjacency_matrix[n];
Instead of maybe something like:
get_adjacent_vertices(n);
Of course, others may have other ideas as to what other things may be done with this but the basic idea is the same -- make your function look like a sequence generator and use the 'sequence' like a real container. :-)
So far this doesn't seem to have much of substance that isn't already in the iterators library, but I could be missing something.
I think it's more semantics than anything -- something that looks and acts like a container can't just be an iterator. I guess the notion of an iterator is directly tied somehow with collections and containers, but seeing just an iterator somehow doesn't give the same semantics -- at least as how I see it. -- Dean Michael C. Berris Software Engineer, Friendster, Inc.
Dean Michael Berris wrote:
Almost does it, but not necessarily. Constructing an instance of the transform iterator would require the instantiation of the counting_iterator as well.
template <class ResultType, class InputType> struct generator { typedef transform_iterator< function<ResultType(InputType)>, counting_iterator<InputType>
iterator; typedef iterator const const_iterator;
iterator begin() { return make_transform_iterator( counting_iterator<InputType>(), _function ); }; [...]
By using ranges instead of iterators, you can get that container-like behaviour (grouping of begin and end). However counting_range doesn't seem to be implemented yet.
On Tue, Jun 24, 2008 at 9:26 PM, Mathias Gaunard <mathias.gaunard@ens-lyon.org> wrote:
Dean Michael Berris wrote:
Almost does it, but not necessarily. Constructing an instance of the transform iterator would require the instantiation of the counting_iterator as well.
template <class ResultType, class InputType> struct generator { typedef transform_iterator< function<ResultType(InputType)>, counting_iterator<InputType>
iterator; typedef iterator const const_iterator;
iterator begin() { return make_transform_iterator( counting_iterator<InputType>(), _function ); }; [...]
By using ranges instead of iterators, you can get that container-like behaviour (grouping of begin and end).
However counting_range doesn't seem to be implemented yet.
Interesting... Would the range provide the overload to operator[] to create an associative pseudo-container that behaves like a container? Perhaps something like (using C++0x auto): auto f_sequence = make_lazy_function_range( begin, end, function() ); f_sequence[1]; // like *(++begin); ? I think the generator works at a different level than ranges and/or iterators. The ideas are complimentary IMO: double function_1(int i) { return (numeric_cast<double>(i)*2.0) + 1.0; }; // 2x + 1 double function_2(int i) { return numeric_cast<double>(i) * numeric_cast<double>(i) + 1.0; }; // 2^x + 1 ... generator<double, int> f_1(function_1); generator<double, int> f_2(function_2); for_each( make_zip_iterator(make_tuple(f_1.begin(), f_2.begin())), make_zip_iterator(make_tuple(f_1.begin() + 5, f_2.begin() + 5))), deal_with_data_points() ); iterator_range< generator<double, int>::const_iterator
first_10_f_1s(f_1.begin(), f_1.begin() + 5);
This way, dereferencing the iterator would cause the function to be invoked and a value to be produced (much like a transform iterator). Also, much like for example some mathematical sequences and/or tables where values can be looked up from, the abstraction provided by a generated sequence container instead of just iterators and ranges can be very useful. If it helps thinking about it like a lazy associative container where values are only computed as necessary, then I think that would be one way you can think about the generator example/proposal. // with phoenix for example generator<int, int> doubles(arg1 * 2); doubles[100]; // 200 HTH -- Dean Michael C. Berris Software Engineer, Friendster, Inc.
Dean Michael Berris wrote:
On Tue, Jun 24, 2008 at 2:22 PM, David Abrahams <dave@boostpro.com> wrote:
Dean Michael Berris wrote:
On Tue, Jun 24, 2008 at 4:02 AM, David Abrahams <dave@boostpro.com> wrote:
std::copy(fib.begin(), fib.end(), ostream_iterator<int>(std::cout, " ")); // prints the infinite sequence If you're using Binet's formula, that's a pretty inefficient way to compute all those Fibs, isn't it? Or does your generator cache nearby Fibs?
Actually, the function object can be as stateful or state-less as you want. There's an iterative way of computing the nth fibonacci number, Well of course; that's the easy way to do it... but it makes random access with fib[n] very inefficient.
The inefficiency is actually inherent in the underlying function implementation, and not directly as an effect of using the generator to wrap the function.
I know; I was just trying to find out if solving that problem was part of your domain.
but that's really beside the point here. ;-) Well, _my_ point was to find out whether your proposal was going to figure out how to handle both random access and sequential iteration efficiently. Sounds like it isn't.
Accessing the generator wouldn't be inefficient whether you access it using operator[] or sequentially. Unless you're thinking that somehow the generator will cache results of previously accessed data and encapsulate an appropriately random-accessible container (like an std::vector) to mitigate the recomputation of already previously accessed data; would this be something that would be considered a value-add for a general-purpose utility?
No, I was just thinking that operator++ would see if there was a cache of the previous two numbers and add them together.
The make_*_iterator family works fine, but the problem becomes one of semantics/readability. If you just wanted iterators, the above would be sufficient. For 'prettier' syntax that models the sequence generators that other programming languages have (think Haskell's list comprehensions/construction) making something look like a list may be important.
The idea really is to abstract the function that generates the list from the list it generates (lazily?) itself. Instead of doing:
fib(n);
Something that looks like
fib[n];
May look more semantically correct.
But... you can already use operator[] on a random access iterator. So if you're not going to explicitly solve the problem of efficient sequential and random-access traversals,
boost::transform_iterator< boost::counting_iterator<T>, boost::function<T(T)>
already does what you want, I think.
Almost does it, but not necessarily. Constructing an instance of the transform iterator would require the instantiation of the counting_iterator as well.
So?
So far this doesn't seem to have much of substance that isn't already in the iterators library, but I could be missing something.
I think it's more semantics than anything -- something that looks and acts like a container can't just be an iterator.
You can always build an iterator_range.
I guess the notion of an iterator is directly tied somehow with collections and containers, but seeing just an iterator somehow doesn't give the same semantics -- at least as how I see it.
OK -- Dave Abrahams BoostPro Computing http://www.boostpro.com
participants (3)
-
David Abrahams -
Dean Michael Berris -
Mathias Gaunard