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

From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2008-07-03 09:20:21

On Thu, Jul 3, 2008 at 2:32 PM, Dean Michael Berris
<mikhailberis_at_[hidden]> wrote:
> On Wed, Jul 2, 2008 at 6:25 PM, Giovanni Piero Deretta
<snip>
> Consider:
>
>  operator|(r, f) -> lazy_range<typeof(r), apply<typeof(f)> >

IMHO operator|  shouldn't be restricted to ranges. Logically it should
just apply its lhs to its rhs, regardless of the type of both lhs and
rhs [1]. It is not the job of operator| to create lazy ranges, but of
'f'.

[1] in fact, lacking concepts, rhs or lhs should provide a way to find
operator| via adl, for example inheriting from a pipeable empty class.
Putting operator| in the global namespace is not an option.

>
> Now that allows you to chain operator|(r, f) infinitely, just making
> sure that along the way you create an instance of a specific type
> (lazy_range) which when applied a begin(...) or end(...) function will
> yield the appropriately constructed iterator.

what is the advantage with respect to having 'f' construct the lazy
range instead? It just complicates the implementation of operator|.

>
> Note that in the examples we've been giving:
>
> source | take(10) | filter(filter_function()) | map(mapper())
>
> We'd have a lazy_range<...> which has a type:
>
> lazy_range<
>  lazy_range<
>    lazy_range<
>      range_type,
>      taken_range_generator
>    >,
>    filer_function
>  >,
>  mapper
>>

how does lazy_range distinguish from a filter range and a map range?
lazy_range<A, B> has to somehow delegate the decision to the B
parameter. At that point you might remove all the smartness from
operator| and move it to B.

Also, how is the above different from
mapped_range<filtered_range<taken_range<range_type>, Filter>,Mapper>
which is still lazy?

>
> An instance of this is returned by the whole expression template (the
> argument to the construction of the instance would be the original
> source range), which we can call begin(...) or end(...) against, and
> get the correct iterator type. If we have the above typedefed as
> 'some_lazy_range', doing:
>
> begin(some_lazy_range(source)) -> the beginning of the lazy range
> end(some_lazy_range()) -> the 'end' iterator given the lazy range
>

How this is an unique property of lazy_range? This would work with all
the range_ex proposals I have seen so far.

>>>
>>> for_each ( range(source) | take(10) | map(mapper()), cout << arg1 <<
>>> endl ); // with Phoenix
>>>
>>> Assuming that there's a boost::for_each(range<T>, F) -- I don't think
>>> I need to know the result type of the reducer in that example. Am I
>>> missing something?
>>
>> There is no reducer (i.e. a fold) in the above expression. If you want
>> to reduce a range you need to know the result type of the reducer
>> function if you want to actually save the final result (which is
>> usually the case :) ).
>>
>
> Right. Maybe that's a bad example. Considering that we can make a
> reducer an external function and adapted using
> 'make_function_output_iterator', we can use it in std::copy (of course
> something like boost::copy(range, function) ):
>
> reducer reducer_instance;
> copy ( source | take(10) | map(mapper()) ,
>  make_function_output_iterator(reducer_instance)
> );

A Reduce is a binary function: it takes the accumulated value and the
i'th element to generate the new accumulated value (think
std::accumulate). So, the above cannot work: an output iterator is
logically unary, not binary, unless the reducer stores the accumulator
value 'inside' (then you should be catching the result of copy to
retrieve the accumulated result). In any case, you need to know the
type of the accumulated value, and you are no better than in my
example.

>
> In this case I really don't need to know the exact type of the
> range(s) created by the pipe syntax, because type deduction will do
> the trick for me.
>

You do not need to know the exact type of the range in my example
either. Just the value of the type returned by the final reducer.  A
reducer doesn't usually (but not always) return a range.

>>>
>>> Shouldn't the deforestation already have happened in the zipping and
>>> application of the function to yield another tuple?
>>>
>>
>> let say you have the rewrite rule:
>>    map<map<Range,A>,B>  ->  map<Range, compose<A,B> >
>>
>> If zip_with returns a map<zip<R1, R2>, A>,  you can simplify the
>> expression map(zip_with(r1, r2, a), b) as:
>>
>>  map<map<zip<R1, R2>, A>, B> -> map<zip<R1, R2>, compose<A,B> >
>>
>> without any other special rule. If zip_with were to return a special
>> zip<R1, R2, A>, you
>> need a specific rule to handle this case. I.e. zip_with shouldn't be a
>> primitive, but should be constructed on top of map and zip.
>>
>
> True, but zip_with can return a range: map<map<zip<transform<R1, F1>,
> transform<R2, F2> > >, A>, B> which can still be re-written.
>

eh? What is transform there? What are F1 and F2?

> BTW, are the rewrite rules already there, or will this have to be
> something that has to still be written using Boost.MPL?

Of course not, for now this is just 'wouldn't it be great if...' :)

-- 
gpd