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

From: Dean Michael Berris (mikhailberis_at_[hidden])
Date: 2008-07-01 01:12:28

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?
);

Without having to go through the explicit 'make_*_iterator' or
explicit type of the iterator you want to build.

> 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

This looks like (when used):

transform(
  zipped_range(source1, source2, source3),
  make_function_output_iterator(make_zipped_function(f1, f2, f3)),
  make_zipped_function(g1, g2, g3)
);

> Finally, what do you mean that range_ex views should be lazier? Lazier
> than what?
>
> [1] Btw, I greatly dislike the verbose make_filtered_view,
> make_transformed_view names. I use these builders a lot, and simply
> call them 'map' and 'filter'.
>

I agree.

> [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

-- 
Dean Michael C. Berris
Software Engineer, Friendster, Inc.