Re: [boost] function based associative generator

From: David Abrahams (dave_at_[hidden])
Date: 2008-06-24 02:22:10

Dean Michael Berris wrote:
> 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,

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