Re: [boost] function based associative generator

From: Dean Michael Berris (mikhailberis_at_[hidden])
Date: 2008-06-24 00:53:30

On Tue, Jun 24, 2008 at 4:02 AM, David Abrahams <dave_at_[hidden]> 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.