uniform way to remove duplicates from a typelist using boost hana

Question

I am trying to familiarise myself with boost::hana. As an exercise I want to create a function that will remove duplicates from a hana::tuple using a user-provided comparison function. The problem I am facing is related to using hana::type_c's for storing types as objects. Here is what I have

#include <boost/hana/equal.hpp>
#include <boost/hana/tuple.hpp>
#include <boost/hana/unpack.hpp>
#include <boost/hana/pair.hpp>
#include <boost/hana/any_of.hpp>
#include <boost/hana/second.hpp>
#include <boost/hana/fold.hpp>
#include <boost/hana/core/make.hpp>
#include <boost/hana/core/tag_of.hpp>

#include <iostream>

template <class>
struct what_is;

namespace hana = boost::hana;

// simply push back an element to the sequence
auto push_back = [](auto seq, auto t) {

    using namespace boost::hana;
    return unpack(seq, [&](auto&&... element){return make<typename tag_of<decltype(seq)>::type>(element..., t);});
};

// this is the main function
auto remove_duplicates = [](auto seq, auto comp) {

    using namespace boost::hana;

    auto f = [&](auto state, auto el){
        return if_( any_of(state, partial(comp, el)),
                   [=](){return state;},
                   [=](){return push_back(state, el);})();
    };

    return fold(seq, make<typename tag_of<decltype(seq)>::type>(), f);
};

// user-defined comparison function
// elements are considered equal if only second element of pairs are equal
auto comp_pair = [](auto&& t1, auto&& t2) {

    using namespace boost::hana;
    return equal(second(t1), second(t2));
};


int main() {

    auto my_tuple1 = hana::tuple_t<int, float, double, int, float>;
    auto no_dups1 = remove_duplicates(my_tuple1, hana::equal); // this is fine, decltype(no_dups1) -> tuple< type<int>, type<float>, type<double> >

    auto my_tuple2 = hana::tuple_t< hana::pair<int, int>, hana::pair<float, int>, hana::pair<float, float> >;
//    auto no_dups2 = remove_duplicates(my_tuple2, comp_pair); // what I want here is tuple< type<pair<int, int>>, type<pair<float, float>> >
}

The last line creates problems as there is no second element to extract from a hana::type<pair<X,Y>>. For this to work I would have to create a very ugly sequence such as tuple< pair<type<int>, type<int>>, pair<type<double>, type<int>>, pair<type<float>, type<double>> >. As you can imagine this can grow bad really quickly, for instance if I had a sequence tuple<int, pair<X,Y>, double, float> etc. Is there any way I can create a uniform way to deal with this? I come from an MPL/fusion background and there I can work directly with the types without the need to wrap the types. Thank you

Answer 1

Unlike Fusion, Hana does not implicitly translate values to types. In general, this is nice because it means you get to use the more expressive value syntax. On the other hand, for some use cases where you really want to extract the wrapped types, you have to do it explicitly with Hana while Fusion does it for you under the hood.

I see two options for what you're trying to achieve. The first solution is to change your comp_pair function so that it unwraps the pairs itself:

template <typename T1, typename U1, typename T2, typename U2>
constexpr auto comp_pair(hana::basic_type<hana::pair<T1, U1>>,
                         hana::basic_type<hana::pair<T2, U2>>)
{
    return hana::type_c<U1> == hana::type_c<U2>;
}

...

auto no_dups2 = remove_duplicates(my_tuple2, [](auto pair1, auto pair2) {
    return comp_pair(pair1, pair2);
});

The second solution, which I find more idiomatic, is to actually hold your types as objects:

// This could arguably be part of Hana, just like we provide tuple_t
template <typename T, typename U>
constexpr auto pair_t = hana::make_pair(hana::type_c<T>, hana::type_c<U>);

auto tuple2 = hana::make_tuple(pair_t<int, int>, pair_t<double, int>, pair_t<float, double>);
auto nodups2 = remove_duplicates(tuple2, [](auto p1, auto p2) {
  return hana::second(p1) == hana::second(p2);
});

However, you say:

As you can imagine this can grow bad really quickly, for instance if I had a sequence tuple<int, pair<X,Y>, double, float> etc. Is there any way I can create a uniform way to deal with this?

I'm not sure I follow here. Are you saying that you might want to have something like tuple<type<int>, pair<type<X>, type<Y>>, type<double>, type<float>>, and are looking for a generic way of achieving this? If so, then I must say I highly suspect there's a better way of achieving whatever you're trying to do. I can try to help if you provide more context.

Hope this helps!