Filtering a list with types using boost::hana

I'm trying to filter out a list with types, but that doesn't seem to work. I am sure that I am doing something wrong here, here is a test I've created to reproduce it:

#include <iostream>

#include <boost/hana.hpp>
#include <boost/hana/ext/std/tuple.hpp>

struct X {
};
struct Y {
};
struct Z {
};

int main(int argc, char **argv) {

    namespace hana = boost::hana;

    constexpr std::tuple<X, Y, Z> list;
    constexpr std::tuple<X> filterlist;

    auto t = hana::filter(list, [&](auto t) {
            return hana::not_(hana::contains(filterlist, hana::decltype_(t)));
        });

    std::cout << "filtered list contains " << hana::size(t) << " items, expected 2 items" << std::endl;

    return 0;
}

Basically what I want: I have a list of types and I want to return a list with items that are not in the filterlist. So in this case, it should be std::tuple<Y, Z>.

The current output of this program is: filtered list contains 3 items, expected 2 items

Regards, Matthijs

Solution

The problem is that you're checking whether a type (decltype_(X{}) == type<X>{}) is in the filter list, which contains actual objects, not types. In other words, it's a bit as if you were trying to compare a std::type_info object representing some type T with an object of actual type T; that makes no sense semantically. Instead, what you want is the following:

#include <iostream>
#include <boost/hana.hpp>
#include <boost/hana/ext/std/tuple.hpp>
namespace hana = boost::hana;

struct X { };
struct Y { };
struct Z { };

int main(int argc, char **argv) {
  constexpr std::tuple<X, Y, Z> list;
  constexpr std::tuple<hana::type<X>> filterlist;
  auto t = hana::remove_if(list, [&](auto t) {
    return hana::contains(filterlist, hana::decltype_(t));
  });

  std::cout << "filtered list contains " << hana::size(t) << " items, expected 2 items" << std::endl;
}

That being said, if you already have a filterlist tuple that's around anyway for other purposes, you can still use it to filter:

#include <iostream>
#include <boost/hana.hpp>
#include <boost/hana/ext/std/tuple.hpp>
namespace hana = boost::hana;

struct X { };
struct Y { };
struct Z { };

int main(int argc, char **argv) {
  constexpr std::tuple<X, Y, Z> list;
  constexpr std::tuple<X> filterlist;
  auto t = hana::remove_if(list, [&](auto t) {
    return hana::any_of(filterlist, [&](auto u) {
        return hana::decltype_(u) == hana::decltype_(t);
    });
  });

  std::cout << "filtered list contains " << hana::size(t) << " items, expected 2 items" << std::endl;
}

As a last note, be wary of these constructs since they are O(n^2) compile-time. If you need efficient lookup, consider using hana::set (the implementation sucks right now but it will get better when I have more time).