#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;
}