#include <iostream>
#include <type_traits>

template <int I> using int_ = std::integral_constant<int, I>;

template<typename T> using eval = typename T::type;

template<typename... List>
struct seq
{
    using type = seq;
};

template<typename> struct car;
template<typename Car, typename... Cdr>
struct car< seq<Car, Cdr...>>
{
    typedef Car type;
};

template<typename> struct cdr;
template<typename Car, typename... Cdr>
struct cdr< seq<Car, Cdr...>>
{
    typedef seq<Cdr...> type;
};


template <typename, typename> struct cons;
template <typename T, typename... L>
struct cons<T, seq<L...>>
{
    typedef seq<T, L...> type;
};

//template <typename T>
//struct cons<T, seq<>>
//{
//    typedef seq<T> type;
//};

template<typename, typename> struct concat;
template <typename... As, typename... Bs>
struct concat<seq<As...>, seq<Bs...>>
{
    typedef seq<As..., Bs...> type;
};

template<typename> struct length;
template<typename... As>
struct length<seq<As...>>
{
    typedef std::integral_constant<unsigned, sizeof...(As)> type;
};

template<typename>
struct is_empty
{
    typedef std::integral_constant<bool, false> type;
};

template<>
struct is_empty<seq<>>
{
    typedef std::integral_constant<bool, true> type;
};

template<template<typename... Args> class Fun, typename... Args>
struct apply
{
    typedef eval<Fun<Args...>> type;
};


template<typename B, typename C, typename A> struct cond;
template<typename C, typename A>
struct cond<std::true_type, C, A>
{
    typedef C type;
};

template<typename C, typename A>
struct cond<std::false_type, C, A>
{
    typedef A type;
};


//template<typename, typename> struct map;

//template<typename A, typename... As, template<typename A> class F>
//struct map<seq<A, As...>, F>
//{
//    //typedef seq<eval<F<A>>...> type;
//    typedef cons < eval < F < A > >
//                 , map < seq < As... > , F >
//                 > type;
//};

template <typename S, template<typename B> class F> struct map_t;

//template <template <typename B> class F, typename... Es>
template <typename... Es, template <typename B> class F>
struct map_t <seq<Es...>, F >
{
    typedef typename car<seq<Es...>>::type Car;
    typedef typename cdr<seq<Es...>>::type Cdr;
    typedef eval< cons < eval < F < Car > >
                 , eval< map_t < Cdr, F > >
                 > > type;
};

template <template <typename B> class F>
struct map_t <seq<>, F >
{
    typedef seq<> type;
};

template <typename S, template<typename B> class F> struct filter_t;

//template <template <typename B> class F, typename... Es>
template <typename... Es, template <typename B> class F>
struct filter_t <seq<Es...>, F >
{
    typedef typename car<seq<Es...>>::type Car;
    typedef typename cdr<seq<Es...>>::type Cdr;
    typedef eval< cond < eval < F < Car > >
                       , eval < cons < Car, eval< filter_t < Cdr, F > > > >
                       , eval < filter_t < Cdr, F > >
                       > > type;
};

template <template <typename B> class F>
struct filter_t <seq<>, F >
{
    typedef seq<> type;
};

template<typename A> struct even;

template<int I>
struct even<std::integral_constant<int, I> >
{
    typedef std::integral_constant<bool, I % 2 == 0> type;
};


//template<typename> struct constant;
//template<typename T>
//struct constant<T>
//{
//    typedef std::integral_constant<bool, false> type;
//};


typedef seq<int_<1>, int_<2>, int_<3> > s1;
typedef seq<int_<7>, int_<5>, int_<9> > s2;
typedef seq<int_<1>, s2, int_<17>, s1 > s3;
typedef seq<> empty;
typedef seq<int_<1>> s0;

template<typename Seq> using concat_fix = apply<concat, s2, Seq>;


int main()
{

    std::cerr << eval < length < eval < apply < concat, s1, s3 >> >> ::value << '\n';
    std::cerr << eval < length < eval < concat_fix < s3 >> >> ::value << '\n';
    std::cerr << eval < apply < length, empty> >::value << '\n';
    std::cerr << eval < length < eval < concat < s1, s3 >> >> ::value << '\n';
    std::cerr << "even(2): " << eval < even < int_<2>> >::value << '\n';
    std::cerr << "even(3): " << eval < even < int_<3>> >::value << '\n';

    std::cerr << "is_same: " << std::is_same < eval < int_ < 2 >> , int_ < 2 >> ::value << '\n';

    typedef seq<int_<1>, int_<2>, int_<3>, int_<4>, int_<5>, int_<6>, int_<7>, int_<8>, int_<9>, int_<10>, int_<11>> sint;
    std::cerr << eval < length < eval < map_t < sint, even > > > >::value << '\n';
    std::cerr << eval < length < eval < filter_t < sint, even > > > >::value << '\n';
    typedef eval<filter_t<sint, even>> test;

    std::cerr << "first in even list: " << eval<car<test>>::value << '\n';
    std::cerr << "second in even list: " << eval<car<eval<cdr<test>>>>::value << '\n';
    std::cerr << "third in even list: " << eval<car<eval<cdr<eval<cdr<test>>>>>>::value << '\n';
    return 0;
}