Boost logo

Boost :

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

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

#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,
      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_ =

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 list run by bdawes at, gregod at, cpdaniel at, john at