Skip to content

Instantly share code, notes, and snippets.

@thefloweringash
Created August 14, 2012 00:54
Show Gist options
  • Save thefloweringash/3345265 to your computer and use it in GitHub Desktop.
Save thefloweringash/3345265 to your computer and use it in GitHub Desktop.
Not sure if winning: variadic templates as lists
// Template Wrangling
// ==================
// convert a template into something that can be ::apply-ed
template <template <typename...> class T>
struct make_apply {
template <typename... Args>
using apply = T<Args...>;
};
// convert a template into something that can be ::apply-id, and
// return via ::type
template <template <typename...> class T>
struct make_apply_type {
template <typename... Args>
struct apply {
using type = T<Args...>;
};
};
// Function Operators
// ==================
template <typename F>
struct constF {
template <typename T, typename... TS>
using apply = typename F::template apply<TS...>;
};
template <typename F, typename G>
struct composeF {
template <typename T>
using apply = typename G::template apply<typename F::template apply<T>::type>;
};
// take a list of args, feed in one at a time
template <typename F>
struct uncurry {
template <typename... XS>
struct apply {};
template <typename X>
struct apply<X> {
using type = typename F::template apply<X>::type;
};
template <typename X, typename... XS>
struct apply<X,XS...> {
using type = typename uncurry<typename F::template apply<X>>::template apply<XS...>::type;
};
};
// take args one at a time, feed in list
template <int n, typename F, typename... Accum>
struct curry_worker {
template <typename T>
using apply = curry_worker<n-1, F, Accum..., T>;
};
template <typename F, typename... Accum>
struct curry_worker<1, F, Accum...> {
template <typename T>
struct apply {
using type = typename F::template apply<Accum..., T>::type;
};
};
template <int n, typename F>
struct curry {
template <typename T>
using apply = curry_worker<n-1, F, T>;
};
// List Functions
// ==============
template <typename... T>
struct list {};
template <typename T, typename TS>
struct cons{};
template <typename T, typename... TS>
struct cons<T, list<TS...>> {
using type = list<T, TS...>;
};
template <typename T> struct length {};
template <typename... xs>
struct length<list<xs...>> {
static constexpr int val = sizeof...(xs);
};
template <typename T> struct head {};
template <typename x, typename... xs>
struct head<list<x, xs...>> {
using type = x;
};
template <typename T> struct tail {};
template <typename x, typename... xs>
struct tail<list<x, xs...>> {
using type = list<xs...>;
};
template <typename T>
struct null {
static constexpr bool val = false;
};
template <>
struct null<list<>> {
static constexpr bool val = true;
};
template <typename F, typename Z, typename T>
struct foldr {};
template <typename F, typename Z, typename x, typename... xs>
struct foldr<F, Z, list<x,xs...>> {
using type =
typename F::template apply<x,
typename foldr<F, Z, list<xs...>>::type
>::type;
};
template <typename F, typename Z>
struct foldr<F, Z, list<>> {
using type = Z;
};
template <typename F, typename XS, typename YS>
struct zipWith{};
template <typename F, typename XS>
struct zipWith<F, XS, list<>>{
using type = list<>;
};
template <typename F, typename YS>
struct zipWith<F, list<>, YS>{
using type = list<>;
};
template <typename F>
struct zipWith<F, list<>, list<>>{
using type = list<>;
};
template <typename F,
typename x, typename... xs,
typename y, typename... ys>
struct zipWith<F, list<x, xs...>, list<y,ys...>>{
using type = typename cons<typename F::template apply<x,y>::type,
typename zipWith<F, list<xs...>, list<ys...>>::type
>::type;
};
template <typename X, typename Y>
struct pair {};
using make_pair = make_apply_type<pair>;
template <typename XS, typename YS>
using zip = zipWith<make_pair, XS, YS>;
template <typename F, typename XS>
using map = foldr<uncurry<composeF<F, curry<2, make_apply<cons>>>>, list<>, XS>;
// Peano Numbers
// =============
template <typename T>
struct S {};
struct Z {};
template <typename T>
struct to_int {};
template <>
struct to_int<Z> {
static constexpr int val = 0;
};
template <typename T>
struct to_int<S<T>> {
static constexpr int val = 1 + to_int<T>::val;
};
struct succ {
template <typename X>
struct apply {
using type = S<X>;
};
};
// Primitive Boxing
// ================
template <typename T, T x>
struct wrap {
static constexpr T unwrap = x;
};
template <typename F, typename... W>
struct with_wrapped{};
template <typename T, typename F, T... x>
struct with_wrapped<F, wrap<T, x>...>{
using type = wrap<T, F::template apply<x...>::val>;
};
template <typename F>
struct wrapF {
template <typename... TS>
using apply = with_wrapped<F, TS...>;
};
template <typename T, T... x>
struct build_prim_list {
using type = list<wrap<T, x>...>;
};
// Testing and Example Functions
// ==============================
template <typename X, typename Y>
struct types_eq {
static constexpr bool val = false;
};
template <typename X>
struct types_eq<X, X> {
static constexpr bool val = true;
};
struct add {
template <int x, int y>
struct apply {
static constexpr int val = x + y;
};
};
struct add_one {
template <int x>
using apply = add::apply<1, x>;
};
template <typename XS>
using sum = foldr<wrapF<add>, wrap<int, 0>, XS>;
template <typename L>
using foldr_list_identity = foldr<make_apply<cons>, list<>, L>;
struct add3 {
template <int x, int y, int z>
struct apply {
static constexpr int val = x + y + z;
};
};
using curried_add3 = curry<3, wrapF<add3>>;
int main() {
static_assert(length<list<int, int, int>>::val == 3,
"length test");
static_assert(types_eq<head<list<char, long, long>>::type, char>::val,
"head test");
static_assert(types_eq<tail<list<char, long, long>>::type, list<long, long>>::val,
"tail test");
static_assert(null<list<>>::val == true,
"null test");
static_assert(null<list<int>>::val == false,
"null test");
static_assert(to_int<Z>::val == 0,
"to_int of 0");
static_assert(to_int<S<Z>>::val == 1,
"to_int of 1");
static_assert(to_int<S<S<Z>>>::val == 2,
"to_int of 2");
static_assert(to_int<foldr<constF<succ>, Z, list<int, int>>::type>::val == 2,
"foldr with types");
static_assert(foldr<constF<wrapF<add_one>>, wrap<int, 0>, list<wrap<int, 0>, wrap<int, 1>>>::type::unwrap == 2,
"foldr with wrapped primitives");
static_assert(types_eq<list<>, tail<list<int>>::type>::val,
"test type equality");
static_assert(!types_eq<list<>, list<int>>::val,
"test type inequality");
using test_list_types = list<int, char, double, float>;
static_assert(types_eq<test_list_types, foldr_list_identity<test_list_types>::type>::val,
"test `foldr (:) [] === id' identity");
static_assert(types_eq<make_apply<cons>::apply<wrap<int, 0>, list<>>::type,
list<wrap<int, 0>>
>::val,
"test make_apply");
static_assert(types_eq<list<pair<int, long>, pair<double, float>>,
zipWith<make_pair, list<int, double>, list<long, float>>::type
>::val,
"test zipWith");
static_assert(types_eq<list<pair<int, long>>,
zip<list<int, double>, list<long>>::type
>::val,
"test zip");
static_assert(constF<wrapF<add_one>>::apply<wrap<int, 3>, wrap<int, 4>>::type::unwrap == 5,
"test constF/wrapF");
static_assert(types_eq<list<wrap<int, 1>, wrap<int, 2>, wrap<int, 3>>,
build_prim_list<int, 1, 2, 3>::type>::val,
"test build_prim_list");
static_assert(sum<build_prim_list<int, 1, 2, 3, 4>::type>::type::unwrap == 10,
"test sum");
static_assert(composeF<wrapF<add_one>, wrapF<add_one>>::apply<wrap<int, 1>>::type::unwrap == 3,
"test composeF");
static_assert(curry<2, wrapF<add>>::apply<wrap<int, 2>>::apply<wrap<int, 1>>::type::unwrap == 3,
"test curry with 2 args");
static_assert(curried_add3::apply<wrap<int,3>>::apply<wrap<int, 2>>::apply<wrap<int, 1>>::type::unwrap == 6,
"test curry with 3 args");
static_assert(uncurry<curried_add3>::apply<wrap<int,3>, wrap<int, 2>, wrap<int, 1>>::type::unwrap == 6,
"test uncurry/curry");
static_assert(types_eq<build_prim_list<int, 1, 2, 3>::type,
map<wrapF<add_one>, build_prim_list<int, 0, 1, 2>::type>::type>::val,
"test map");
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment