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

On Wed, Jun 17, 2015 at 9:58 AM, Louis Dionne wrote:

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

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

I would expect that the constraints on copy() be that size(x) == size(y), and that y[i] = static_cast(x[i]) is well-formed for all i < size(x) (not that it's not necessary for me that std::is_convertible::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 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