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

Subject: Re: [boost] [Hana] Formal review for Hana
From: Louis Dionne (ldionne.2_at_[hidden])
Date: 2015-06-17 10:58:34

Zach Laine <whatwasthataddress <at> gmail.com> 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<A, B> x = ...;
> > > hana::_tuple<C, D> y = ...;
> > >
> > > // some stuff happens ...
> > >
> > > // This should compile iff std::is_same<A, C>::value && std::is_same<B,
> > > D>::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<A, B, C> 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<A, B, C> 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