Re: [boost] [TypeSort] Automatic type sorting

Subject: Re: [boost] [TypeSort] Automatic type sorting
From: Eric Niebler (eniebler_at_[hidden])
Date: 2015-03-22 14:34:35

(Trying again. EnigMail for Thunderbird seems deeply confused on my
machine, sorry.)

On 3/21/2015 11:52 PM, Louis Dionne wrote:
> Anyway, here's a version that does what was probably needed by
> the OP (notice the additional indexed_sort of the indices):
> 
> ------------------------------------------------------------------------------
> #include <boost/hana/integral_constant.hpp>
> #include <boost/hana/pair.hpp>
> #include <boost/hana/range.hpp>
> #include <boost/hana/tuple.hpp>
> #include <boost/hana/type.hpp>
> 
> #include <type_traits>
> using namespace boost::hana;
> using namespace boost::hana::literals;
> 
> 
> auto indexed_sort = [](auto list, auto predicate) {
>     auto indexed_list = zip(list, to<Tuple>(range(0_c, size(list))));
>     auto sorted = sort_by(predicate ^on^ head, indexed_list);
>     return make_pair(transform(sorted, head), transform(sorted, last));
> };
> 
> int main() {
>     auto types = tuple_t<char[4], char[2], char[1], char[5], char[3]>;
>     auto sorted = indexed_sort(types, [](auto t, auto u) {
>         return sizeof_(t) < sizeof_(u);
>     });
>     using Tup = decltype(unpack(first(sorted), template_<_tuple>))::type;
>     auto indices = second(indexed_sort(second(sorted), less));
> 
>     // When accessed through the indices sequence, the tuple appears to be
>     // ordered as the `types` above. However, as can be seen in the
>     // static_assert below, the tuple is actually ordered differently.
>     Tup tup;
>     char(&a)[4] = tup[indices[0_c]];
>     char(&b)[2] = tup[indices[1_c]];
>     char(&c)[1] = tup[indices[2_c]];
>     char(&d)[5] = tup[indices[3_c]];
>     char(&e)[3] = tup[indices[4_c]];
> 
>     static_assert(std::is_same<
>         Tup,
>         _tuple<char[1], char[2], char[3], char[4], char[5]>
>     >{}, "");
> }
<snip>

Nice! Funny, I wrote pretty much the same code last night, right down to
the use of the "on" combinator (which I discovered with the help of
Hoogle, assuming rightly the Haskell guys had a name for such a useful
utility).

#include <tuple>
#include <meta/meta.hpp>

using namespace meta;
namespace l = lazy;

template<typename List, typename Pred = quote<less>>
using indexed_sort1_ = let<
  var<struct _sorted_zip,
    sort<zip<
      list<List, as_list<make_index_sequence<List::size()>>>>,
      on<Pred, quote<first>>>>,
  pair<l::transform<_sorted_zip, quote<first>>,
       l::transform<_sorted_zip, quote<second>>>>;

template<typename PairOfLists>
using indexed_sort2_ =
  pair<first<PairOfLists>,
       second<indexed_sort1_<second<PairOfLists>>>>;

template<typename List, typename Pred = quote<less>>
using indexed_sort =
  indexed_sort2_<indexed_sort1_<List, Pred>>;

int main()
{
    using L = list<char[4],char[2],char[1],char[5],char[3]>;
    using P = indexed_sort<L, on<quote<less>, quote<sizeof_>>>;
    using Tup = apply_list<quote<std::tuple>, first<P>>;
    using Idx = second<P>;
        // list<int_<3>,int_<1>,int_<0>,int_<4>,int_<2>>

    Tup tup; // std::tuple<char[1],char[2],char[3],char[4],char[5]>
    char(&a)[4] = std::get<at_c<Idx, 0>::value>(tup);
    char(&b)[2] = std::get<at_c<Idx, 1>::value>(tup);
    char(&c)[1] = std::get<at_c<Idx, 2>::value>(tup);
}

The strange-looking let<var<_x,expr>,body> is a let expression that lets
you create the equivalent of named local variables. It's good for
storing intermediate results when you don't feel like farming work out
to a separate helper alias. The whole thing could be written as one big
let expression, actually. I tried it, but IMO this was more grokable.

The Hana solution is elegant, too.

(Strangely, clang-3.4 pukes on my code. Not sure about 3.5 or 3.6, but
trunk likes it just fine, as does gcc 4.9.)

-- 
Eric Niebler
Boost.org
http://www.boost.org