Re: [boost] [range/iterators/algorithms/phoenix/bind...] Coordinated Approach

From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2008-07-01 06:22:42

On Tue, Jul 1, 2008 at 7:12 AM, Dean Michael Berris
<mikhailberis_at_[hidden]> wrote:
> On Mon, Jun 30, 2008 at 10:51 PM, Giovanni Piero Deretta
> <gpderetta_at_[hidden]> wrote:
>> On Mon, Jun 30, 2008 at 3:37 PM, David Abrahams <dave_at_[hidden]> wrote:
>>>>> range_ex
>>>
>>> * Not in Boost.  Should have pipe syntax.  Maybe should use expression
>>> templates and be lazier.
>>
>> Does it really need expression templates? That is, given the range
>> builders make_*_view [1], it should return a *_view (for example a
>> filtered_view). Combining multiple views, you get for example:
>>
>>   filtered_view<mapped_view<taken_view<BaseRange> , Mapper>, Filter> >
>>
>> I.e.  a series of range views are already an expression templates.
>> Now, if you make some (reasonable, and hopefully documented)
>> assumptions about Filter and Mapper, you should be always able to
>> convert sequences of nested views that contains only views known to
>> range_ex in a normal form: for example:
>>
>>   taken_view<mapped_view<filtered_view<BaseRange, compose<Mapper,
>> Filter> >, Mapper> >
>>
>> You can of course collapse multiple mapped, filtered and taken range
>> in a single instance of each range. [2]
>> A top level boost::for_each could be able to unwind the normalized
>> expression and apply a simple iteration over the Base range instead of
>> relying on the compiler of eliminating the abstraction overhead of
>> four different iterators.
>>
>
> I think the point of using expression templates is to be able to do
> something like:
>
> copy( range(source) | taken(10) | map(mapper()),
>  make_function_output_iterator(reducer()) // should have a better name?
> );
>

You do not need anything more than what is in Lambda/Phoenix here.
Instead of having a different function for piping an generating views,
you use the same function and curry it:

  auto reduced = source | take(_, 10) | map(_, mapper()) | fold(_, reducer()) ;

the _ is like _1 in bind/lambda/phoenix, but it doesn't make the whole
expression a lambda expression (it stops at one level). The pipe in
practice works like a compose operator. If you put the range at the
end, you wouldn't even need the '_' (just provide one less argument,
hey it is haskell :) ), but you give up variadic (or overloaded)
functions.

>
>> I think that the basic ranges that should (at least) be supported are:
>>
>>   - mapped_range
>>   - filtered_range
>>   - taken_range (i.e. just the first n elements of a range)
>>   - taken_while_range (i.e. the first elements such as a predicate is true)
>>   - zipped_range
>>   - unfold_range (with which you can pretty much express any other
>> range, see http://tinyurl.com/5mus25)
>>
>> An eventual 'drop' (take all the elements after the first n) and
>> 'drop_while' (drop the first elements such as a predicate is true)
>> probably need strict evaluation anyway and aren't worth supporting
>> explicitly.
>>
>
> I also think there should be a zipped_function which:
>
> - takes N function objects and an N-tuple
> - applies each function to the appropriate tuple
> - returns a tuple of results

D'oh, of course, forgot this.
I think that  zipped_range on top of zipped_iterator is enough, you
get the other functionality by composing with transformed_iterator.

<snip>
>> [2] I think that this is quite similar to the deforestation technique
>> used by functional languages compilers. (see the wikipedia page and
>> the linked articles). In FP it is used mostly to eliminate
>> intermediate (lazily evaluated) lists, but the same technique can be
>> applied in c++. In fact the rewrite rules used map perfectly to c++
>> templates.
>>
>
> Here I think you need the zipped_function idiom where you can create
> an 'in-step' function that can deal with tuples of inputs.
>
> zipped_function(zipped_input) -> zipped_output
>
> Another thing that's missing is a way to transform tuples of one form
> into another -- possibly ignoring tuple elements. I've posted a
> possible implementation based on Fusion's at_c, which allows:
>
> map<int, string> source;
> // populate source..
> for_each(source.begin(), source.end(),
>  select<1> | (cout << arg1 << endl) //using fusion
> );
> // select will choose the second element of the pair
>

Ok, but this is beyond boost range. I think that fusion svn already
provides function objects for every algorithm/accessors, so this would
becomes

  for_each(source | map(_, select<1>() ) , coust << arg1 << endl )

BTW I call select<1>() simply first (and of course also have second,
third, etc...).

-- 
gpd