Last active
December 10, 2015 16:16
-
-
Save mklca/06b0cad3271f8a02bc48 to your computer and use it in GitHub Desktop.
Type-level list and basic operations
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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 */ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment