Re: [boost] function based associative generator

From: Dean Michael Berris (mikhailberis_at_[hidden])
Date: 2008-06-24 07:31:23

On Tue, Jun 24, 2008 at 2:22 PM, David Abrahams <dave_at_[hidden]> wrote:
> Dean Michael Berris wrote:
>> On Tue, Jun 24, 2008 at 4:02 AM, David Abrahams <dave_at_[hidden]> 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.