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-16 10:35:05

Zach Laine <whatwasthataddress <at> gmail.com> writes:

>
> On Tue, Jun 16, 2015 at 8:04 AM, Louis Dionne <ldionne.2 <at> gmail.com> wrote:
>
> > [...]
> >
> > That is the incorrect workaround. The proper, Hana-idiomatic way to write
> > what you need is:
> >
> >     namespace detail {
> >         auto make_matrix_type = [](auto rows) {
> >             auto nrows = hana::size(rows);
> >             static_assert(nrows >= 1u,
> >             "matrix_t<> requires at least one row");
> >
> >             auto ncolumns = hana::size(rows[hana::size_t<0>]);
> >             auto uniform = hana::all_of(rows, [=](auto row) {
> >                 return hana::size(row) == ncolumns;
> >             });
> >             static_assert(uniform,
> >             "matrix_t<> requires tuples of uniform length");
> >
> >             using tuple_type = decltype(hana::flatten(rows));
> >
> >             return hana::type<matrix_t<tuple_type, nrows, ncolumns>>;
> >         };
> >     }
> >
> >     template <typename ...Rows>
> >     using matrix = typename decltype(
> >         detail::make_matrix_type(hana::make_tuple(std::declval<Rows>()...))
> >     )::type;
> >
>
> While that definitely works, it also definitely leaves me scratching my
> head.  Why doesn't
>
> static const std::size_t columns = hana::size(HeadRow{});
>
> Work in the code above, especially since
>
> auto ncolumns = hana::size(rows[hana::size_t<0>]);
>
> does?  That seems at least a little obscure as an interface.

Notice that

    static const std::size_t columns = hana::size(HeadRow{});

requires the `hana::size(HeadRow{})` expression to be a constant expression.
This requires HeadRow to be both default-constructible and a literal type.
On the other hand,

    auto ncolumns = hana::size(rows[hana::size_t<0>]);

just defines a (non-constexpr) variable inside a lambda. It also does not
require anything about the constructibility of `HeadRow`. note that I could
have written the above Hana-metafunction as follows:

    auto make_matrix_type = [](auto head_row, auto ...tail_rows) {
        auto nrows = hana::size_t<sizeof...(tail_rows) + 1>;
        static_assert(nrows >= 1u,
        "matrix_t<> requires at least one row");

        auto ncolumns = hana::size(head_row);

        auto rows = hana::make_tuple(head_row, tail_rows...);
        auto uniform = hana::all_of(rows, [=](auto row) {
            return hana::size(row) == ncolumns;
        });
        static_assert(uniform,
        "matrix_t<> requires tuples of uniform length");

        using tuple_type = decltype(hana::flatten(rows));

        return hana::type<matrix_t<tuple_type, nrows, ncolumns>>;
    };

which is closer to your initial implementation. Now, it is obvious that

    auto ncolumns = hana::size(head_row);

should work, right?

> I also could not get hana::size(hana::type<HeadRow>); to work, btw.

`hana::size` is a function from the Foldable concept. `hana::type<...>`
represents a C++ type. Since a C++ type is not Foldable (that wouldn't
make any sense), you can't call `hana::size` on a `hana::type<...>`.

To understand why what you're asking for can't be done without breaking the
conceptual integrity of Hana, consider what would happen if I defined
`std::vector<>` as a Foldable. Obviously, the following can't be made
to work:

    hana::size(hana::type<std::vector<int>>)

Hana works with objects, and the `hana::type<>` wrapper is there to allow us
to represent __actual C++ types__ as objects, for the purpose of calling
type traits on them, essentially. The idiomatic Hana-way to do what you're
trying to achieve is to consider your matrix rows as objects, which they are,
instead of types.

> [...]
>
> > > That being said, I really, really, want to do this:
> > >
> > > tuple_1 foo;
> > > tuple_2 bar;
> > >
> > > boost::hana::copy_if(foo, bar, [](auto && x) { return my_predicate(x);
> > });
> > >
> > > Currently, I cannot.  IIUC, I must do:
> > >
> > > tuple_1 foo;
> > > auto bar = boost::hana::take_if(foo, [](auto && x) { return
> > > my_predicate(x); });
> > >
> > > Which does O(N^2) copies, where N = boost::hana::size(bar), as it is
> > > pure-functional.  Unless the optimizer is brilliant (and it typically is
> > > not), I cannot use code like this in a hot section of code.  Also, IIUC
> > > take_if() cannot accommodate the case that decltype(foo) != decltype(bar)
> >
> > I don't understand; take_if() is not an algorithm provided by Hana.
> >
>
> Right!  I meant filter().  Sorry.

No problem. Now I understand better. So basically you want to write

    tuple_1 foo;
    auto bar = boost::hana::filter(foo, my_predicate);

I don't understand why that's O(N^2) copies. That should really be N copies,
where `N = hana::size(bar)`. As a bonus, if you don't need `foo` around
anymore, you can just write

    tuple_1 foo;
    auto bar = boost::hana::filter(std::move(foo), my_predicate);

and now you get N moves, not even N copies.

> [...]
>
> > Since Hana expects
> > functions to be pure in general and assignment is a side effect, this
> > cannot
> > be achieved with a normal algorithm. However, Hana provides some algorithms
> > that alow side-effects. One of them is for_each, and the other is `.times`
> > (from IntegralConstant). I suggest you could write the following:
> >
> >     hana::size(foo).times.with_index([&](auto i) {
> >         using T = std::remove_reference_t<decltype(bar[i])>;
> >         bar[i] = static_cast<T>(foo[i]);
> >     });
> >
>
> Ok.  You also had this in the PR you made for Units-BLAS:
>
> hana::size(xs).times.with_index([&](auto i) {
>     xs[i] = ys[i];
> });
>
> ... which is even simpler.  However, either is a pretty awkward way to
> express an operation that I think will be quite often desired.  copy(),
> copy_if(), move(), and move_if() should be first-order operations.  I also
> want the functional algorithms, but sometimes I simply cannot use them....

First, assignment to tuples will be fixed and I consider it a bug right now.
However,

copy:
    auto tuple1 = hana::make_tuple(...);
    auto tuple2 = tuple1;

copy_if:
    auto tuple1 = hana::make_tuple(...);
    auto tuple2 = hana::filter(tuple1, predicate);

move:
    auto tuple1 = hana::make_tuple(...);
    auto tuple2 = std::move(tuple1);

move_if:
    auto tuple1 = hana::make_tuple(...);
    auto tuple2 = hana::filter(std::move(tuple1), predicate);

Does that solve your problem, or am I misunderstanding it?

> Now where's my pony?

Here :-) http://goo.gl/JNq0Ve

> [...]

Regards,
Louis