Compile time list as well as some higher order functions implemented with Grand Functional Spirit of SICP

meta_list.cc

#include <iostream>


struct meta_nil { };

template <int I, typename _ty_cdr>
struct meta_cons {
        static const int car = I;
        typedef _ty_cdr cdr;
};

#define car(p) p::car
#define cdr(p) p::cdr


template <typename _ty_lst>
void print_list (void) {
        std::cout << _ty_lst::car << "\t";
        print_list<typename _ty_lst::cdr>();
}

template <>
void print_list <meta_nil> (void) {
        std::cout << std::endl;
}


//
// Concatenate two lists together
// 
template <typename _ty_lst1, typename _ty_lst2>
struct meta_append {
        typedef meta_cons<
                _ty_lst1::car,
                typename meta_append <typename _ty_lst1::cdr, _ty_lst2>::ty_val
                >
        ty_val;
};

template <typename _ty_lst2>
struct meta_append<meta_nil, _ty_lst2> {
        typedef _ty_lst2 ty_val;
};


//
// Apply _func to each element in _ty_lst
// 
template <template <int> class _func, typename _ty_lst>
struct meta_map {
        typedef meta_cons <
                _func<_ty_lst::car>::value,
                typename meta_map<_func, typename _ty_lst::cdr>::ty_val
                >
        ty_val;
};

template <template <int> class _func>
struct meta_map <_func, meta_nil> {
        typedef meta_nil ty_val;
};


//
// Fold from left to right
// 
template <template <int, int> class _func,
          int _x0,
          typename _ty_lst>
struct meta_foldl {
        static const int value =
                        meta_foldl<_func,
                                   _func<_ty_lst::car, _x0>::value,
                                   typename _ty_lst::cdr>::value;
};

template <template <int, int> class _func,
          int _x0>
struct meta_foldl<_func, _x0, meta_nil> {
        static const int value = _x0;
};


//
// Filter _ty_lst using _func
// 
template <template <int> class _func, typename _ty_lst>
struct meta_filter;

template <template <int> class _func,
          typename _ty_lst,
          bool _tf>
struct __meta_filter_branch {
};

template <template <int> class _func, typename _ty_lst>
struct __meta_filter_branch<_func, _ty_lst, true> {
        typedef meta_cons <
                _ty_lst::car,
                typename meta_filter<_func, typename _ty_lst::cdr>::ty_val
                >
        ty_val;
};

template <template <int> class _func, typename _ty_lst>
struct __meta_filter_branch<_func, _ty_lst, false> {
        typedef typename meta_filter<_func, typename _ty_lst::cdr>::ty_val ty_val;
};


template <template <int> class _func, typename _ty_lst>
struct meta_filter {
        typedef typename __meta_filter_branch<
                _func, _ty_lst,
                _func<_ty_lst::car>::value>::ty_val
        ty_val;
};

template <template <int> class _func>
struct meta_filter<_func, meta_nil> {
        typedef meta_nil ty_val;
};


//
// Insert (to an ordered list)
// 
template <int elem, typename _ty_lst>
struct meta_insert;

template <int elem, typename _ty_lst, bool _sel>
struct __meta_insert_branch {
};

template <int elem, typename _ty_lst>
struct __meta_insert_branch <elem, _ty_lst, true> {
        typedef meta_cons<elem, _ty_lst> ty_val;
};

template <int elem, typename _ty_lst>
struct __meta_insert_branch<elem, _ty_lst, false> {
        typedef meta_cons<_ty_lst::car,
                          typename meta_insert<elem, typename _ty_lst::cdr>::ty_val
                          >
        ty_val;
};

template <int elem, typename _ty_lst>
struct meta_insert {
        typedef typename __meta_insert_branch <
                elem, _ty_lst,
                (elem < _ty_lst::car)>::ty_val  ty_val;
};

template <int elem>
struct meta_insert<elem, meta_nil> {
        typedef meta_cons<elem, meta_nil> ty_val;
};


//
// Insertion Sort
//
template <typename _ty_lst>
struct meta_sort {
        typedef typename meta_insert<
                _ty_lst::car,
                typename meta_sort<typename _ty_lst::cdr>::ty_val
                >::ty_val
        ty_val;
};

template <>
struct meta_sort<meta_nil> {
        typedef meta_nil ty_val;
};


// A simple higher order function
template <template <int, int> class _binop_func,
          int var0>
struct curry_binop {
        template <int var1>
        struct ty_func {
                static const int value = _binop_func<var0, var1>::value;
        };
};


template <int I, int J>
struct plus {
        static const int value = I + J;
};
        
template <int I>
struct plus_one {
        static const int value = I + 1;
};

template <int I>
struct square {
        static const int value = I * I;
};

template <int I>
struct is_positive {
        static const bool value = (I > 0);
};



int main(int argc, char *argv[])
{
        std::cout << "list construction\n";
        typedef meta_cons<1, meta_cons<2, meta_cons<3, meta_cons<4, meta_nil> > > > p;
        print_list<p>();
        
        std::cout << "map example\n";
        typedef meta_map<plus_one, p>::ty_val p2;
        print_list<p2>();        

        std::cout << "currying example\n";
        std::cout << curry_binop<plus, 1>::ty_func<2>::value << std::endl;

        std::cout << "higher order function example\n";
        typedef meta_map<curry_binop<plus, 3>::ty_func, p>::ty_val p3;
        print_list<p3>();

        std::cout << "foldl example\n";
        std::cout << meta_foldl<plus, 0, p>::value << std::endl;
        std::cout << meta_foldl<plus, 0, p2>::value << std::endl;
        std::cout << meta_foldl<plus, 0, p3>::value << std::endl;

        std::cout << "squared sum example\n";
        std::cout << meta_foldl<plus, 0, meta_map<square, p>::ty_val >::value << std::endl;
        std::cout << meta_foldl<plus, 0, meta_map<square, p2>::ty_val >::value << std::endl;
        std::cout << meta_foldl<plus, 0, meta_map<square, p3>::ty_val >::value << std::endl;

        std::cout << "filter example\n";
        typedef meta_map<curry_binop<plus, -2>::ty_func, meta_append<p, p2>::ty_val>::ty_val p4;
        print_list<p4>();
        print_list<meta_filter<is_positive, p4>::ty_val>();

        std::cout << "one-liner form of the previous example\n";
        print_list<meta_filter<is_positive,
                               meta_map<curry_binop<plus, -2>::ty_func,
                                        meta_append<p, p2>::ty_val
                                        >::ty_val>::ty_val>();

        std::cout << "insert example\n";
        typedef meta_cons<1, meta_cons<3, meta_cons<5, meta_cons<7, meta_nil> > > > pi;
        print_list<pi>();
        print_list<meta_insert<4, pi>::ty_val>();

        std::cout << "sort example\n";
        typedef meta_cons<6, meta_cons<3, meta_cons<7, meta_cons<1, meta_cons<5, meta_nil> > > > > ps;
        print_list<ps>();
        print_list<meta_sort<ps>::ty_val>();
                
        return 0;
}