Re: [boost] [Boost] [Hana] Formal review for Hana

17 Jun 2015

      Zach Laine  writes:
...
...
[...]
The current implementation of filter for Tuple will be as good as I
described.
The generic implementation for other sequence types (say an adapted
std::tuple)
will be slower. So there's room for improvement, of course.
When you say "slower" do you mean 2*N or N^2?
Definitely more like 2*N. But I'll let you count :-). For generic sequences,
the implementation is roughly equivalent to (once simplified):

filter(xs, pred)
    == flatten(transform(xs, [](auto&& x) {
            if (pred(x)) return make_tuple(x);
            else         return make_tuple();
        }))

    // Let's denote make_tuple(x1, ..., xn) by [x1, ..., xn]. Let's also
    // assume the worst case, i.e. the predicate is always satisfied.
    // Then, we have N moves or copies so far:
    == flatten([[x1], [x2], ... [xn]])

    == fold_right([[x1], [x2], ... [xn]], [], concat)

    // This is about N more copies:
    == concat([x1], concat([x2], ... concat([xn], [])))

So it's O(k*N) for some constant k (say k <= 10 to be safe), but not O(N^2).
...
...
...
(I know that above bar is
initialized with the result of filter(), but in many cases, the result
will
be assigned to an existing value, and the final copy is not guaranteed to
be elided.  In much of my code, I need that guarantee, or a way to fall
back to direct assignment where the elision does not occur.)
The result of `filter` is an rvalue temporary tuple. If the input sequence
to
filter was a movable-from tuple, it turns out that this rvalue result will
have been move-constructed. The rest is up to the thing that receives the
result of filter(). If you assign the result of filter() to something that
has a move-assignment operator, then no copy occurs. I might be
misunderstanding your requirement.
Sometimes extraneous moves are not ok either.  I really, really, need to
use mutating operations and side effects at least some of the time.
I understand that sometimes this is needed. For those times, you can use
for_each or .times with an index and mutate stuff as you wish. It's very,
very hard to write Hana algorithms if you must guarantee that things are
called in a specific order, or even called at all, so we have to ensure
pure functions are used in the general case. It's also sometimes a
compile-time performance tradeoff.
...
...
...
...
[...]
First, assignment to tuples will be fixed and I consider it a bug right
now.
However,
[...]
Does that solve your problem, or am I misunderstanding it?
That all works fine, but I actually need assignment across tuple types
that
are different, but have compatible elements:
hana::_tuple x = ...;
hana::_tuple y = ...;
// some stuff happens ...
// This should compile iff std::is_same::value && std::is_same::value
x = y;
// But this should work as long as a C is assignable to an A and a D is
assignable to a B:
hana::copy(x, y);
I guess I will need to decide upon this when I resolve the issue about
tuple
assignment. It is not yet clear to me why `x = y` should not work when the
tuple types are different but have compatible elements. I must think about
it.
Well, sometimes C is only explicitly convertible to A.  I perhaps
overstated things above.  What I should have said is, in the general case,
"x = y" is not defined for some values, if the assignment relies on
implicit conversion.  Moreover, I still want to do other mutating
operations from one tuple to another, aside from just assignment.
Without redesigning the whole library, and without relying on something
similar to iterators, I can't currently see a way to provide generic
algorithms that could output their result into an existing sequence.

But regardless, I'd like to understand what semantics you would be expecting
from something like

    hana::copy(x, y)

More generally, would the following do what you need?

    auto transform_mutate = [](auto& in, auto& out, auto f) {
        for_each(size(in).times.with_index, [&](auto i) {
            in[i] = f(out[i]);
        });
    };

Also, it just occurred to me that some algorithms simply can't write their
result into an existing sequence, because the type of that resulting sequence
isn't even known yet. Consider:

    hana::tuple xs;
    hana::tuple<?, ?, ?> result;

    // should write the resulting sequence into 'result'.
    filter_mutate(xs, result, predicate);

You don't know what's the type of the tuple before you have performed the
algorithm. The only way I see this can be done is by using some kind of
result_of namespace like in Fusion, so you can write:

    hana::tuple xs;
    result_of::filter<...>::type result;

    filter_mutate(xs, result, predicate);

But that's not a path I want to take. I think it might be possible to address
80% of your problem by adding one or two simple functions to Hana for making
mutation easier, without having to change everything.

Regards,
Louis

Re: [boost] [Boost] [Hana] Formal review for Hana

Louis Dionne