Type-level list and basic operations

test_type_list.cc

// Test suite for type_lists

// The tests are all static asserts so that successful compilation of this
// translation unit indicates all tests passed.

#include <cstdlib>

#include <type_list.hpp>

using std::is_same;

using type_list::nil;
using type_list::cons;
using type_list::make;
using type_list::map;
using type_list::foldl;
using type_list::foldr;
using type_list::size;
using type_list::take;
using type_list::drop;
using type_list::impl::merge;
using type_list::sort;

////////////////////////////////////////////////////////////////////////////////
// Static tests of make
////////////////////////////////////////////////////////////////////////////////
static_assert(
    is_same<
      // Apply make to an empty argument list
      typename make<>::type_list,
      // The result should be an empty list
      nil>::value,
    "make with no arguments produces an empty list");

static_assert(
    is_same<
      // Apply make to an non-trivial argument list
      typename make<int, float, void(double)>::type_list,
      // Manually construct the expected result
      cons<int,
        cons<float,
          cons<void(double),
            nil>>>>::value,
    "make with trivial arguments produces the appropriate list");

////////////////////////////////////////////////////////////////////////////////
// Static tests of map
////////////////////////////////////////////////////////////////////////////////

struct dummy_result_int {};
struct dummy_result_float {};
struct dummy_result_bool {};

template<typename>
struct dummy_op;

template<>
struct dummy_op<int> {
  typedef dummy_result_int type;
};

template<>
struct dummy_op<float> {
  typedef dummy_result_float type;
};

template<>
struct dummy_op<bool> {
  typedef dummy_result_bool type;
};

static_assert(
    is_same<
      // Apply dummy_op to the empty list
      typename map<dummy_op, nil>::type_list,
      // The result should be an empty list
      nil>::value,
    "map of nil is nil");

static_assert(
    is_same<
      // Apply dummy_op to the a test list
      typename map<dummy_op,
        typename make<int, float, bool>::type_list>::type_list,
      // Construct the result list
      typename make<
          dummy_result_int, dummy_result_float, dummy_result_bool
        >::type_list>::value,
    "map of test_list is correct");

////////////////////////////////////////////////////////////////////////////////
// Static tests of foldl
////////////////////////////////////////////////////////////////////////////////

// Test that left fold computes the appropriate value by creating a left fold
// operation and only specializing it for the precise applications that foldl
// should compute.
template<typename, typename>
struct left_op;

struct left_zero {};

static_assert(
    is_same<
      // Apply foldl to an empty list
      typename foldl<left_op, left_zero, nil>::type,
      // The result should be left_zero
      left_zero>::value,
    "left fold of an empty list is its zero");

// Types in the list
struct test_one {};
struct test_two {};
struct test_three {};

// Specializations of left_op and types for it to return for all evaluations in
// a left fold
struct left_one {};

template<>
struct left_op<left_zero, test_one> {
  typedef left_one type;
};

struct left_two {};

template<>
struct left_op<left_one, test_two> {
  typedef left_two type;
};

struct left_three {};

template<>
struct left_op<left_two, test_three> {
  typedef left_three type;
};

static_assert(
    is_same<
      // Apply foldl to the test list
      typename foldl<
        left_op,
        left_zero,
        typename make<test_one, test_two, test_three>::type_list>::type,
      // And check its result matches manual evaluation
      left_three>::value,
    "foldl properly evaluates a simple type list");

////////////////////////////////////////////////////////////////////////////////
// Static tests of foldr
////////////////////////////////////////////////////////////////////////////////

// The tests of foldr are similar to those for left fold.

template<typename, typename>
struct right_op;

struct right_zero {};

static_assert(
    is_same<
      // Apply foldr to an empty list
      typename foldr<right_op, nil, right_zero>::type,
      // Ensure the result is the right zero
      right_zero>::value,
    "right fold of an empty list is its zero");

// Reuse the test_* classes from the foldl test as input and create new result
// types

struct right_one {};

template<>
struct right_op<test_three, right_zero> {
  typedef right_one type;
};

struct right_two {};

template<>
struct right_op<test_two, right_one> {
  typedef right_two type;
};

struct right_three {};

template<>
struct right_op<test_one, right_two> {
  typedef right_three type;
};

static_assert(
    is_same<
      // Apply foldl to the test list
      typename foldr<
          right_op,
          typename make<test_one, test_two, test_three>::type_list,
          right_zero
        >::type,
      // And check its result matches manual evaluation
      right_three>::value,
    "foldr properly evaluates a simple type list");

////////////////////////////////////////////////////////////////////////////////
// Static tests of size
////////////////////////////////////////////////////////////////////////////////
static_assert(
    size<nil>::value == 0,
    "size of an empty list is zero");

static_assert(
    size<typename make<test_one, test_two, test_three>::type_list>::value == 3,
    "size works on a non-trivial list");

////////////////////////////////////////////////////////////////////////////////
// Static tests of take
////////////////////////////////////////////////////////////////////////////////
static_assert(
    is_same<typename take<6, nil>::type_list, nil>::value,
    "applying take to an empty list yields an empty list");

static_assert(
    is_same<
      typename take<5,
        typename make<test_one, test_two, test_three>::type_list
      >::type_list,
      typename make<test_one, test_two, test_three>::type_list
    >::value,
    "take works on undersized input");

static_assert(
    is_same<
      typename take<2,
        typename make<test_one, test_two, test_three>::type_list
      >::type_list,
      typename make<test_one, test_two>::type_list
    >::value,
    "take works on oversized input");

static_assert(
    is_same<
      typename take<3,
        typename make<test_one, test_two, test_three>::type_list
      >::type_list,
      typename make<test_one, test_two, test_three>::type_list
    >::value,
    "take works on right-sized input");


////////////////////////////////////////////////////////////////////////////////
// Static tests of drop
////////////////////////////////////////////////////////////////////////////////
static_assert(
    is_same<typename drop<6, nil>::type_list, nil>::value,
    "dropping elements from an empty list yields the empty list");

static_assert(
    is_same<
      typename drop<5,
        typename make<test_one, test_two, test_three>::type_list
      >::type_list,
      nil>::value,
    "drop works on undersized input");

static_assert(
    is_same<
      typename drop<2,
        typename make<test_one, test_two, test_three>::type_list
      >::type_list,
      typename make<test_three>::type_list
    >::value,
    "drop works on oversized input");

static_assert(
    is_same<
      typename drop<3,
        typename make<test_one, test_two, test_three>::type_list
      >::type_list,
      nil>::value,
    "drop works on right-sized input");

////////////////////////////////////////////////////////////////////////////////
// Static tests of sort
////////////////////////////////////////////////////////////////////////////////

// Mock orderable type defined with a particular integral value
template<int value>
using num = std::integral_constant<int, value>;

// Simple comparison operator
template<typename L, typename R>
struct int_cmp {
  static const int value = L::value - R::value;
};

// Comparison operator with non-total ordering
// Integers are classified into equivalency classes modulo Mod which are
// naturally ordered
template<int Mod, typename L, typename R>
struct intmod_cmp {
  static const int value = L::value%Mod - R::value%Mod;
};

template<typename L, typename R>
using intmod3_cmp = intmod_cmp<3, L, R>;

// Tests of merge
static_assert(
    is_same<
      // Apply merge to two empty type lists
      typename merge<int_cmp, nil, nil>::type_list,
      // The result should be an empty type list
      nil
    >::value,
    "merge of empty lists is an empty list");

static_assert(
    is_same<
      // Apply merge to an empty list (on the left)
      typename merge<int_cmp, nil,
          typename make<num<4>, num<9>, num<11>>::type_list
        >::type_list,
      // The result should be other list
      typename make<num<4>, num<9>, num<11>>::type_list
    >::value,
    "the empty list is a left-identity of merge");

static_assert(
    is_same<
      // Apply merge to an empty list (on the rightz)
      typename merge<int_cmp,
        typename make<num<2>, num<7>, num<10>>::type_list,
        nil
      >::type_list,
      // The result should be the list
      typename make<num<2>, num<7>, num<10>>::type_list
    >::value,
    "the empty list is a left-identity of merge");

static_assert(
    is_same<
      // Apply merge to two non-trivial sorted lists
      typename merge<int_cmp,
        typename make<num<2>, num<7>, num<11>>::type_list,
        typename make<num<5>, num<6>, num<15>>::type_list
      >::type_list,
      // Manually construct the result
      typename make<
        num<2>, num<5>, num<6>, num<7>, num<11>, num<15>
      >::type_list
    >::value,
    "merge correctly merges a strictly ordered list");

static_assert(
    is_same<
      // Apply merge with a partial ordering
      typename merge<intmod3_cmp,
        typename make<
            // With modulo-three equivalence this list is <0, 1, 2>
            num<9>, num<7>, num<8>
          >::type_list,
        typename make<
            // With modulo-three equivalence this list is <1, 2>
            num<10>, num<5>
          >::type_list
      >::type_list,
      // Manually construct the result accounting for stability requirements
      typename make<
        num<9>, num<7>, num<10>, num<8>, num<5>
      >::type_list
    >::value,
    "merge stably merges lists under partial ordering conditions");

// Tests of sort
static_assert(
    is_same<
      // Apply sort to an empty list
      typename sort<int_cmp, nil>::type_list,
      nil
    >::value,
    "sort properly sorts an empty list");

static_assert(
    is_same<
      // Apply sort to a singleton list
      typename sort<int_cmp, cons<num<1>, nil>>::type_list,
      // The result should be the same singleton list
      cons<num<1>, nil>
    >::value,
    "sort properly sorts a singleton list");

static_assert(
    is_same<
      // Apply sort to an ordered list
      typename sort<int_cmp, cons<num<1>, cons<num<2>, nil>>>::type_list,
      // The result should be the same list
      cons<num<1>, cons<num<2>, nil>>
    >::value,
    "sort works on sorted input");

static_assert(
    is_same<
      // Apply sort to an unordered list
      typename sort<int_cmp, cons<num<2>, cons<num<1>, nil>>>::type_list,
      // The result should be a properly ordered list
      cons<num<1>, cons<num<2>, nil>>
    >::value,
    "sort works on simple unsorted lists");

static_assert(
    is_same<
      // Apply sort to a non-trivial list
      typename sort<int_cmp,
        typename make<num<6>, num<1>, num<4>, num<0>, num<7>, num<2>>::type_list
      >::type_list,
      typename make<num<0>, num<1>, num<2>, num<4>, num<6>, num<7>>::type_list
    >::value,
    "sort properly sorts a fully ordered list");

static_assert(
    is_same<
      // Apply sort to a non-trivial list
      typename sort<intmod3_cmp,
          typename make<
              num<11>, num<6>, num<1>, num<4>, num<8>, num<0>, num<7>, num<2>
        >::type_list
      >::type_list,
      typename make<
          num<6>, num<0>, num<1>, num<4>, num<7>, num<11>, num<8>, num<2>
        >::type_list
    >::value,
    "sort stably sorts a partially ordered list");

int main(int, char*[])
{
  return EXIT_SUCCESS;
}

type_list.hh

// Type-level lists

#ifndef TYPE_LIST_HH
#define TYPE_LIST_HH

#include <type_traits>

/*******************************************************************************
 * Type List
 *******************************************************************************
 * Type-level functional list implementation
 */

namespace type_list {
  /***************************************************************************
   * Type List Constructors
   ***************************************************************************
   * Lists are implemented as sequences of cons cells. This implies that the
   * length of a list is determined by the compiler's maximum recursive
   * template depth.
   */

  // The empty list.
  struct nil {};

  // A cons cell. TailList should be either nil or an instance of cons
  // itself.
  template<typename Head, typename TailList>
  struct cons {};

  /***************************************************************************
   * Convenience variadic constructor of type lists
   ***************************************************************************
   * A variadic template encoding its type arguments into a type list.
   */
  template<typename... Elems>
  struct make;

  template<>
  struct make<> {
    typedef nil type_list;
  };

  template<typename Elem, typename... Elems>
  struct make<Elem, Elems...> {
    typedef cons<Elem, typename make<Elems...>::type_list> type_list;
  };

  /***************************************************************************
   * Type list map.
   ***************************************************************************
   * Transforms a list by applying a type function to each element in the
   * list.
   */
  template<template<typename> class Func, typename List>
  struct map;

  template<template<typename> class Func>
  struct map<Func, nil> {
    typedef nil type_list;
  };

  template<template<typename> class Func, typename Head, typename TailList>
  struct map<Func, cons<Head, TailList>> {
    typedef cons<
        typename Func<Head>::type,
        typename map<Func, TailList>::type_list
      > type_list;
  };

  /***************************************************************************
   * Type list left fold.
   ***************************************************************************
   *   cons                              Func< , >
   *  /    \                                 /  \
   * 1    cons                        Func< , >  4
   *     /    \                           /  \
   *    2    cons                  Func< , >  3
   *        /    \                     /  \
   *       3    cons            Func< , >  2
   *           /    \               /  \
   *          4      nil        Init    1
   */
  template<
      template<typename, typename> class Func,
      typename Init,
      typename List>
  struct foldl;

  template<
      template<typename, typename> class Func,
      typename Init>
  struct foldl<Func, Init, nil> {
    typedef Init type;
  };

  template<
      template<typename, typename> class Func,
      typename Init,
      typename Head,
      typename TailList>
  struct foldl<Func, Init, cons<Head, TailList>> {
    typedef typename foldl<
        Func,
        typename Func<Init, Head>::type,
        TailList
      >::type type;
  };

  /***************************************************************************
   * Type list right fold.
   ***************************************************************************
   *   cons                   Func< , >
   *  /    \                      /  \
   * 1    cons                   1  Func< , >
   *     /    \                         /  \
   *    2    cons                      2  Func< , >
   *        /    \                            /  \
   *       3    cons                         3  Func< , >
   *           /    \                               /  \
   *          4      nil                           4    Init
   */
  template<
      template<typename, typename> class Func,
      typename List,
      typename Init>
  struct foldr;

  template<
      template<typename, typename> class Func,
      typename Init>
  struct foldr<Func, nil, Init> {
    typedef Init type;
  };

  template<
      template<typename, typename> class Func,
      typename Head,
      typename TailList,
      typename Init>
  struct foldr<Func, cons<Head, TailList>, Init> {
    typedef typename Func<
        Head,
        typename foldr<Func, TailList, Init>::type
      >::type type;
  };

  /***************************************************************************
   * Type list size
   ***************************************************************************
   * Computes the length of a type list
   */
  namespace impl {
    template<unsigned int val>
    using size_state = std::integral_constant<unsigned int, val>;

    template<typename State, typename ListElem>
    struct size_kern {
      typedef size_state<State::value + 1> type;
    };
  }

  template<typename List>
  struct size {
    static unsigned int const value =
      foldl<impl::size_kern, impl::size_state<0>, List>::type::value;
  };

  /***************************************************************************
   * Type list take
   ***************************************************************************
   * Extracts a prefix of a specified length from a type list
   */

  template<
    int len,
    typename List>
  struct take;

  template<int len>
  struct take<len, nil> {
    typedef nil type_list;
  };

  template<
    typename Head,
    typename TailList>
  struct take<0, cons<Head, TailList>> {
    typedef nil type_list;
  };

  template<
    int len,
    typename Head,
    typename TailList>
  struct take<len, cons<Head, TailList>> {
    typedef cons<Head, typename take<len - 1, TailList>::type_list> type_list;
  };

  /***************************************************************************
   * Type list drop
   ***************************************************************************
   * Drops a prefix of a specified length from the front of a type list
   */

  template<
    int len,
    typename List>
  struct drop;

  template<int len>
  struct drop<len, nil> {
    typedef nil type_list;
  };

  template<
    typename Head,
    typename TailList>
  struct drop<0, cons<Head, TailList>> {
    typedef cons<Head, TailList> type_list;
  };

  template<
    int len,
    typename Head,
    typename TailList>
  struct drop<len, cons<Head, TailList>> {
    typedef typename drop<len - 1, TailList>::type_list type_list;
  };

  /***************************************************************************
   * Type list sort
   ***************************************************************************
   * Stable generic sortation for type lists.
   */

  // Utility operations used to implement sortation
  namespace impl {
    // Constructs a sorted list from two sorted lists. In order to achieve a
    // stable sort this routine must favor the first argumment when the
    // leading element of the each input list compare equally.
    template<
        template<typename, typename> class Cmp,
        typename Left,
        typename Right,
        // Anonymous parameter used to disable alternative template
        // specializations via SFINAE.
        typename = void
      >
    struct merge;

    // Specialization for the double nil case to resolve ambiguity between
    // the cases handling a single nil list
    template<template<typename, typename> class Cmp>
    struct merge<Cmp, nil, nil> {
      typedef nil type_list;
    };

    // Upon termination of one input list copy the remaining list to output
    template<
        template<typename, typename> class Cmp,
        typename TypeList
      >
    struct merge<Cmp, nil, TypeList> {
      typedef TypeList type_list;
    };

    template<
        template<typename, typename> class Cmp,
        typename TypeList
      >
    struct merge<Cmp, TypeList, nil> {
      typedef TypeList type_list;
    };

    // In the general case we select the least element and recurse
    template<
        template<typename, typename> class Cmp,
        typename LHead,
        typename LTail,
        typename RHead,
        typename RTail
      >
    struct merge<Cmp, cons<LHead, LTail>, cons<RHead, RTail>,
        // This specialization is only enabled when the left head is strictly
        // greater than the right head
        typename std::enable_if<(Cmp<LHead, RHead>::value > 0)>::type> {
      // Output the right head and recurse
      typedef cons<
          RHead,
          typename merge<Cmp, cons<LHead, LTail>, RTail>::type_list
        > type_list;
    };

    template<
        template<typename, typename> class Cmp,
        typename LHead,
        typename LTail,
        typename RHead,
        typename RTail
      >
    struct merge<Cmp, cons<LHead, LTail>, cons<RHead, RTail>,
        // This specialization is only enabled when the left head is lesser
        // or equal to the right head
        typename std::enable_if<(Cmp<LHead, RHead>::value <= 0)>::type> {
      // Output the right head and recurse
      typedef cons<
          LHead,
          typename merge<Cmp, LTail, cons<RHead, RTail>>::type_list
        > type_list;
    };
  } // namespace impl

  // Sorts a list into ascending order (according to a comparator)
  template<template<typename, typename> class Cmp, typename List>
  struct sort;

  template<template<typename, typename> class Cmp>
  struct sort<Cmp, nil> {
    typedef nil type_list;
  };

  template<
    template<typename, typename> class Cmp,
    typename Head>
  struct sort<Cmp, cons<Head, nil>> {
    typedef cons<Head, nil> type_list;
  };

  template<
    template<typename, typename> class Cmp,
    typename Head,
    typename TailList>
  struct sort<Cmp, cons<Head, TailList>> {
    typedef typename impl::merge<
        Cmp,
        typename sort<
            Cmp,
            typename take<
                size<cons<Head, TailList>>::value/2,
                cons<Head, TailList>
              >::type_list
          >::type_list,
        typename sort<
            Cmp,
            typename drop<
                size<cons<Head, TailList>>::value/2,
                cons<Head, TailList>
              >::type_list
          >::type_list
      >::type_list type_list;
  };
} // namespace type_list

#endif /* TYPE_LIST_HH */