Skip to content

Instantly share code, notes, and snippets.

@cls

cls/functional-templates.hpp

Last active March 9, 2018 00:44
Show Gist options
  • Save cls/5c72f2f784ca53e7fc8c2ffd64de151a to your computer and use it in GitHub Desktop.
Save cls/5c72f2f784ca53e7fc8c2ffd64de151a to your computer and use it in GitHub Desktop.
Download ZIP
Type-level linked lists, with map, filter, and foldr
Raw
functional-templates.hpp
#include <type_traits>
namespace type_list {
class nil {};
template<class Head, class Tail>
class cons {};
// map f [] = []
// map f (x:xs) = f x : map f xs
template<template<class> class Func, class List>
class map {};
template<template<class> class Func>
class map<Func, nil> {
public:
using type = nil;
};
template<template<class> class Func, class Head, class Tail>
class map<Func, cons<Head, Tail>> {
public:
using type = cons<typename Func<Head>::type, typename map<Func, Tail>::type>;
};
// filter p [] = []
// filter p (x:xs) = if p x then x : filter p xs
// else filter p xs
template<template<class> class Pred, class List>
class filter {};
template<template<class> class Pred>
class filter<Pred, nil> {
public:
using type = nil;
};
template<template<class> class Pred, class Head, class Tail>
class filter<Pred, cons<Head, Tail>> {
public:
using type = typename std::conditional<Pred<Head>::value,
cons<Head, typename filter<Pred, Tail>::type>,
typename filter<Pred, Tail>::type
>::type;
};
// foldl f z [] = z
// foldl f z (x:xs) = foldl f (f z x) xs
template<template<class, class> class Func, class Acc, class List>
class fold_left {};
template<template<class, class> class Func, class Acc>
class fold_left<Func, Acc, nil> {
public:
using type = Acc;
};
template<template<class, class> class Func, class Acc, class Head, class Tail>
class fold_left<Func, Acc, cons<Head, Tail>> {
public:
using type = typename fold_left<Func, typename Func<Acc, Head>::type, Tail>::type;
};
// foldr f z [] = z
// foldr f z (x:xs) = f x (foldr f z xs)
template<template<class, class> class Func, class End, class List>
class fold_right {};
template<template<class, class> class Func, class End>
class fold_right<Func, End, nil> {
public:
using type = End;
};
template<template<class, class> class Func, class End, class Head, class Tail>
class fold_right<Func, End, cons<Head, Tail>> {
public:
using type = typename Func<Head, typename fold_right<Func, End, Tail>::type>::type;
};
} // namespace list
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment