Tag Archives: typelist

C++: список типов

Данный пост посвящён созданию списков типов в C++11 и работе с ними.
Список — это линейная рекурсивная структура данных. Условно её можно представить как

type List = Nil | (type, List)

Здесь Nil — вспомогательный тип, означающий пустой список (или конец списка).

// выбор первой части пары
head x = x
head (h, t) = h

// выбор второй части пары
tail x = Nil
tail (h, t) = t

Теперь на C++.

struct Nil {};

template <class H, class T = Nil>
struct Cons {};

template <class L>
struct Head { using type = L; };

template <class H, class T>
struct Head<Cons<H, T>> { using type = H; };

template <class L>
struct Tail { using type = Nil; };

template <class H, class T>
struct Tail<Cons<H, T>> { using type = T; };

Cons (сокращение от construct) позволяет собирать пару типов в новый тип. Фактически, например, список [char, short, int, long] записывается как Cons<char, Cons<short, Cons<int, Cons<long, Nil>>>>. Это не слишком удобно. Добавим вспомогательные определения, позволяющие сократить запись.

// *T -- синоним выборки зависимого имени type
template <class L>
using HeadT = typename Head<L>::type;

template <class L>
using TailT = typename Tail<L>::type;

template <class... Types>
struct List {};

template <>
struct List<> { using type = Nil; };

template <class H, class... T>
struct List<H, T...> 
{ using type = Cons<H, typename List<T...>::type>; };

template <class... Types>
using ListT = typename List<Types...>::type;

Теперь тот же список типов, что был приведён выше, можно записать как ListT<char, short, int, long>.
Обработка списка распадается на обращение к голове и рекурсивную обработку хвоста. Напишем функцию, выводящую в консоль названия типов, зафиксированных в списке (я воспользуюсь частичной специализацией шаблонов функций, появившейся в C++11).

template <class List>
void print_typelist()
{
  std::cout << typeid(HeadT<List>).name() << ' ';
  print_typelist<TailT<List>>();
}

template <>
void print_typelist<Nil>() {}

Предположим, что есть метафункция f : type -> type и требуется получить список результатов применения данной функции к исходному списку (операция map). Как это реализовать?

map f Nil = Nil
map f (h, t) = (f h, map f t)

Чтобы оформить это на C++, необходимо решить, на какой вариант представления метафункций при этом ориентироваться. В данном случае, я выбрал вариант 2 как основной, применяемый Стандартной библиотекой.

template <template <class A> class F, class L>
struct Map
{ using type = typename F<L>::type; };

template <template <class A> class F, class H, class T>
struct Map<F, Cons<H, T>>
{
  using type = Cons<typename F<H>::type,
                    typename Map<F, T>::type>;
};

template <template <class A> class F>
struct Map<F, Nil> { using type = Nil; };

Предположим, есть метафункция b(x, y), принимающая два параметра. Тогда можно поставить задачу о свёртке списка, т.е. вычисления выражения вида b(start, b(item1, b(item2, …, b(itemN-1, itemN)…))). В функциональных языках функцию, позволяющую выполнить такую свёртку списка для произвольных функции b и начального значения start, обычно называют foldr (правоассоциативная свёртка). Я буду использовать следующее определение на C++.

template <
  template <class A, class B> class F,
  class S, class L>
struct Fold
{
  using type = S;
  static const auto value = type::value;
};

template <
  template <class A, class B> class F,
  class S, class H, class T>
struct Fold<F, S, Cons<H, T>>
{
  using type = typename
    F<S, typename Fold<F, H, T>::type>::type;
  static const auto value = type::value;
};

Воспользуемся Fold для определения операций проверки выполнения некоторого предиката на каком-либо или на всех элементах списка.

template <bool B>
using Bool = std::integral_constant<bool, B>;

using False = Bool<false>;
using True = Bool<true>;

template <class A, class B>
struct Or: Bool<A::value || B::value> {};

template <class A, class B>
struct And: Bool<A::value && B::value> {};

template <class L>
using ExistsTrue = typename Fold<Or, False, L>::type;

template <class L>
using AllTrue = typename Fold<And, True, L>::type;

Например, мы хотим проверить, принадлежит ли некоторый тип заданному списку. Определим для этого метафункцию Belongs тип список:

template <
  template <class A, class B> class F,
  class A>  // карринг
struct Bind
{
  template <class B>
  using apply = typename F<A, B>::type;
};

template <class T, class L>
struct Belongs
  : ExistsTrue<typename 
      Map<Bind<std::is_same, T>::template apply, L>::type> {};

На данной основе не сложно определить и другие операции, обычно определяемые для списков (например, вычисление длины).

Исходный код