#include <iostream>
namespace predicates
{
template<bool B>
struct bool_const { using value = bool_const; };
//
namespace helpers
{
template<typename A, typename B>
struct bool_and;
template<typename B>
struct bool_and<bool_const<true>, B> { using value = typename B::value; };
template<typename B>
struct bool_and<bool_const<false>, B> { using value = bool_const<false>; };
template<typename A, typename B>
struct bool_and { using value = typename bool_and<typename A::value, B>::value; };
//
template<typename A>
struct bool_not;
template<bool B>
struct bool_not<bool_const<B>> { using value = bool_const<!B>; };
template<typename A>
struct bool_not { using value = typename bool_not<typename A::value>::value; };
template<typename A, typename B>
struct eq;
template<typename A>
struct eq<A, A> { using value = bool_const<true>; };
template<typename A, typename B>
struct eq { using value = bool_const<false>; };
template<typename A, typename T, typename F>
struct cond;
template<typename T, typename F>
struct cond<bool_const<true>, T, F> { using value = T; };
template<typename T, typename F>
struct cond<bool_const<false>, T, F> { using value = F; };
template<typename A, typename T, typename F>
struct cond { using value = typename cond<typename A::value, T, F>::value; };
}
//
template<typename A, typename B>
using bool_and = typename helpers::bool_and<A, B>::value;
template<typename A>
using bool_not = typename helpers::bool_not<A>::value;
template<typename A, typename B>
using bool_or = bool_not<bool_and<bool_not<A>, bool_not<B>>>;
template<typename A, typename B>
using eq = typename helpers::eq<A, B>::value;
template<typename A, typename B>
using ne = bool_not<eq<A, B>>;
template<typename A, typename T, typename F>
using cond = typename helpers::cond<A, T, F>::value;
//
template<bool B>
std::ostream &operator<<(std::ostream &stream, const bool_const<B> &)
{
return stream << (B ? "true" : "false");
}
}
namespace numbers
{
template<int N>
struct num { using value = num; };
//
namespace helpers
{
template<typename N1, typename N2>
struct add;
template<int N1, int N2>
struct add<num<N1>, num<N2>> { using value = num<N1 + N2>; };
template<typename N1, typename N2>
struct sub;
template<int N1, int N2>
struct sub<num<N1>, num<N2>> { using value = num<N1 - N2>; };
template<typename N1, typename N2>
struct mult;
template<int N1, int N2>
struct mult<num<N1>, num<N2>> { using value = num<N1 * N2>; };
template<typename N1, typename N2>
struct div;
template<int N>
struct div<num<N>, num<0>> {};
template<int N1, int N2>
struct div<num<N1>, num<N2>> { using value = num<N1 / N2>; };
}
//
template<typename N1, typename N2>
using add = typename helpers::add<N1, N2>::value;
template<typename N1, typename N2>
using sub = typename helpers::sub<N1, N2>::value;
template<typename N1, typename N2>
using mult = typename helpers::mult<N1, N2>::value;
template<typename N1, typename N2>
using div = typename helpers::div<N1, N2>::value;
//
template<int N>
std::ostream &operator<<(std::ostream &stream, const num<N> &)
{
return stream << N;
}
namespace predicates
// inline namespace predicates
{
namespace helpers
{
template<typename A, typename B>
struct lt;
template<int A, int B>
struct lt<num<A>, num<B>> { using value = ::predicates::bool_const<A < B>; };
template<typename A, typename B>
struct le;
template<int A, int B>
struct le<num<A>, num<B>> { using value = ::predicates::bool_const<A <= B>; };
template<typename A, typename B>
struct gt;
template<int A, int B>
struct gt<num<A>, num<B>> { using value = ::predicates::bool_const<(A > B)>; };
template<typename A, typename B>
struct ge;
template<int A, int B>
struct ge<num<A>, num<B>> { using value = ::predicates::bool_const<A >= B>; };
}
template<typename A, typename B>
using lt = typename helpers::lt<A, B>::value;
template<typename A, typename B>
using le = typename helpers::le<A, B>::value;
template<typename A, typename B>
using gt = typename helpers::gt<A, B>::value;
template<typename A, typename B>
using ge = typename helpers::ge<A, B>::value;
}
using namespace predicates;
template<typename N>
using absolute_value = typename ::predicates::cond<lt<N, num<0>>, sub<num<0>, N>, N>;
}
namespace pairs
{
template<typename A, typename B>
struct pair { using value = pair; };
namespace helpers
{
template<typename P>
struct fst;
template<typename A, typename B>
struct fst<pair<A, B>> { using value = A; };
template<typename P>
struct snd;
template<typename A, typename B>
struct snd<pair<A, B>> { using value = B; };
}
template<typename P>
using fst = typename helpers::fst<P>::value;
template<typename P>
using snd = typename helpers::snd<P>::value;
//
template<typename A, typename B>
std::ostream &operator<<(std::ostream &stream, const pair<A, B> &)
{
return stream << "(" << A() << ", " << B() << ")";
}
}
namespace lists
{
template<typename List>
struct list;
struct nil {};
template<typename Head, typename Tail>
struct cons {};
template<>
struct list<nil> { using value = list; };
template<typename Head, typename Tail>
struct list<cons<Head, Tail>> { using value = list; };
//
namespace helpers
{
template<typename List>
struct length;
template<>
struct length<list<nil>> { using value = ::numbers::num<0>; };
template<typename Head, typename Tail>
struct length<list<cons<Head, Tail>>> { using value = ::numbers::add<::numbers::num<1>, typename length<Tail>::value>; };
//
template<typename List>
struct head;
template<typename Head, typename Tail>
struct head<list<cons<Head, Tail>>> { using value = Head; };
//
template<typename List>
struct tail;
template<typename Head, typename Tail>
struct tail<list<cons<Head, Tail>>> { using value = Tail; };
//
template<typename L1, typename L2>
struct append;
template<typename List>
struct append<list<nil>, List> { using value = List; };
template<typename Head, typename Tail, typename List>
struct append<list<cons<Head, Tail>>, List> { using value = list<cons<Head, typename append<Tail, List>::value>>; };
//
template<template<typename, typename> class F, typename Init, typename List>
struct fold;
template<template<typename, typename> class F, typename Init>
struct fold<F, Init, list<nil>> { using value = Init; };
template<template<typename, typename> class F, typename Init, typename Head, typename Tail>
struct fold<F, Init, list<cons<Head, Tail>>> { using value = typename fold<F, typename F<Init, Head>::value, Tail>::value; };
//
template<template<typename> class F, typename List>
struct map;
template<template<typename> class F>
struct map<F, list<nil>> { using value = list<nil>; };
template<template<typename> class F, typename Head, typename Tail>
struct map<F, list<cons<Head, Tail>>> { using value = list<cons<typename F<Head>::value, typename map<F, Tail>::value>>; };
template<typename X, typename List, template<typename, typename> class Cmp, typename Acc>
struct partition_;
template<typename X, template<typename, typename> class Cmp, typename Acc>
struct partition_<X, list<nil>, Cmp, Acc> { using value = Acc; };
template<typename X, typename Head, typename Tail, template<typename, typename> class Cmp, typename Acc>
struct partition_<X, list<cons<Head, Tail>>, Cmp, Acc>
{
using value = typename partition_<X, Tail, Cmp,
::predicates::cond<Cmp<Head, X>, ::pairs::pair<list<cons<Head, ::pairs::fst<Acc>>>, ::pairs::snd<Acc>>,
::pairs::pair<pairs::fst<Acc>, list<cons<Head, ::pairs::snd<Acc>>>>>>::value;
};
template<typename X, typename List, template<typename, typename> class Cmp>
using partition = typename partition_<X, List, Cmp, ::pairs::pair<list<nil>, list<nil>>>::value;
template<typename List, template<typename, typename> class Cmp>
struct qsort;
template<template<typename, typename> class Cmp>
struct qsort<list<nil>, Cmp> { using value = list<nil>; };
template<typename Head, typename Tail, template<typename, typename> class Cmp>
struct qsort<list<cons<Head, Tail>>, Cmp> { using value = typename append<
typename qsort<::pairs::fst<partition<Head, Tail, Cmp>>, Cmp>::value,
list<cons<Head, typename qsort<::pairs::snd<partition<Head, Tail, Cmp>>, Cmp>::value>>>::value; };
}
//
template<typename List>
using lenght = typename helpers::length<List>::value;
template<typename List>
using head = typename helpers::head<List>::value;
template<typename List>
using tail = typename helpers::tail<List>::value;
template<typename L1, typename L2>
using append = typename helpers::append<L1, L2>::value;
template<template<typename, typename> class F, typename Init, typename List>
using fold = typename helpers::fold<F, Init, List>::value;
template<template<typename> class F, typename List>
using map = typename helpers::map<F, List>::value;
template<typename List, template<typename, typename> class Cmp>
using quick_sort = typename helpers::qsort<List, Cmp>::value;
//
template<typename List>
std::ostream &operator<<(std::ostream &, const list<List> &);
template<>
std::ostream &operator<<(std::ostream &stream, const list<nil> &)
{
return stream << "[]";
}
template<typename Head, typename Tail>
std::ostream &operator<<(std::ostream &stream, const list<cons<Head, Tail>> &)
{
return stream << "(" << Head() << "):" << Tail();
}
}
using namespace ::predicates;
using namespace ::numbers;
using namespace ::pairs;
using namespace ::lists;
template<typename N>
using inc = add<N, num<1>>;
template<typename A, typename B>
using abs_lt = lt<absolute_value<A>, absolute_value<B>>;
int main()
{
std::cout << list<nil>() << std::endl;
using test_list = list<cons<num<10>, list<cons<num<2>, list<cons<num<3>, list<cons<num<-7>, list<cons<num<8>, list<cons<num<2>, list<nil>>>>>>>>>>>>>;
std::cout << "length " << test_list() << " = " << lenght<test_list>() << std::endl;
std::cout << test_list() << " = " << head<test_list>() << " ++ " << tail<test_list>() << std::endl;
std::cout << "5 + 8 = " << add<num<5>, num<8>>() << std::endl;
std::cout << "fold (+) 0 " << test_list() << " = " << fold<add, num<0>, test_list>() << std::endl;
std::cout << lt<num<15>, num<2>>() << std::endl;
std::cout << lt<num<15>, num<20>>() << std::endl;
std::cout << "map (+ 1) c = " << map<inc, test_list>() << std::endl;
using new_list = append<test_list, map<inc, test_list>>;
std::cout << new_list() << std::endl;
std::cout << quick_sort<new_list, lt>() << std::endl;
std::cout << quick_sort<new_list, gt>() << std::endl;
std::cout << quick_sort<new_list, abs_lt>() << std::endl;
return 0;
}
Comments