On Tue, Jul 1, 2008 at 7:12 AM, Dean Michael Berris <mikhailberis@gmail.com> wrote:
On Mon, Jun 30, 2008 at 10:51 PM, Giovanni Piero Deretta <gpderetta@gmail.com> wrote:
On Mon, Jun 30, 2008 at 3:37 PM, David Abrahams <dave@boostpro.com> 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