[boost] Re: Boost Algorithms Library

From: David Abrahams (dave_at_[hidden])
Date: 2005-03-22 17:33:09

Joel de Guzman <joel_at_[hidden]> writes:

> David Abrahams wrote:
>
>> Whether results should be lazy (as in Fusion) or greedy, as in
>> standard algorithms, or whether both variants should be provided
>> somehow, are interesting questions.  The answers change the usage
>> pattern, i.e.:
>>   copy(transform(s1,op), output)
>> or   output = transform(s1,op)  // if output supports it
>> vs.
>>   transform(s1,op,output)
>
> WRT Fusion, I am re-considering its laziness. MPL algorithms are
> sequence preserving. Fusion is not, due to laziness. i.e:
>
>     transform(tuple, op)
>
> does not return a sequence like tuple. instead, it returns a
> view (transform_view).
>
> However, I realize now, that in most use cases, I noticed that I
> had to eagerly generate the result into a tuple almost as immediately
> after each transform step.

Really; both the compile-time part (type) and the runtime part
(value)?

> After leaving this for a while in my thought queue, and after
> implementing phoenix2's lazy STL algorithms, I realized that
> the lazy Fusion algorithms could as well be implemented as
> phoenix2's lazy fusion algorithms. 

Interesting.  I'm not sure I understand what you mean yet, though.

> If I implemented Fusion algorithms as non-lazy and sequence
> preserving like MPL, I could easily write lazy fusion algorithms
> through phoenix.

I'd be interested to see that.

> I am still unsure about which is the best way to go. I just
> thought I'd share my recent thoughts on the issue.

Well, the use of segmented iterators and hierarchical algorithms
(http://lafstern.org/matt/segmented.pdf) has some interesting
implications.  You can't just use iterator adaptors such as
transform_iterator to implement laziness unless either:

  1. You want to pay a big efficiency hit

or

  2. The adaptors expose the same "extended properties"
     (e.g. segmented_iterator_traits) as the iterators they're
     adapting.  That requires knowledge of all extended properties.

It seems to me that in order to do the traversal optimally, more than
laziness is required: you'd have to build expression templates and
then somehow analyze the traversal properties of the leaf sequences in
order to evaluate the expressions.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com