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

Subject: Re: [boost] [Hana] Formal review for Hana
From: Zach Laine (whatwasthataddress_at_[hidden])
Date: 2015-06-18 10:07:34

On Wed, Jun 17, 2015 at 9:58 AM, Louis Dionne <ldionne.2_at_[hidden]> wrote:

> 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).

That will be unacceptably slow for many-to-most C++ users.

> > > > > [...]
> > > > >
> > > > > 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)
>

I would expect that the constraints on copy() be that size(x) == size(y),
and that y[i] = static_cast<decltype(y[i])>(x[i]) is well-formed for all i
< size(x) (not that it's not necessary for me that
std::is_convertible<decltype(x[i]), decltype(y[i])>::value be true for all
i).  Perhaps there should be a difference between these two notions of
compatibility, called convert() for the former and copy() for the latter.

> 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]);
>         });
>     };
>

Yes.

> 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.

Right.  I can certainly live with only copy(), convert(), move(), and
transform_mutate().

Zach