Implementing the basic elements of functional programming with C++ templates

With C++ templates, I've implemented a template list type with cons, reverse, merge, sort, filter, map, fold; and higher order template functions with currying. The C++ compiler can also work as an interpreter of a (convoluted) purely functional programming language, which is the C++ template metalanguage.

This main function

int main()
{
  using A = FibList;
  using B = Reverse;
  using C = Cons;
  using D = Merge>;
  using E = Merge;
  using F = Sort;
  using G = Filter;
  using H = Map>::template Apply>;
  using I = FoldRight;
  printLine();
  printLine();
  printLine();
  printLine();
  printLine();
  printLine();
  printLine();
  printLine();
  printLine();
}

will output

( 1 1 2 3 5 8 13 21 34 55 89 144 )
 ( 144 89 55 34 21 13 8 5 3 2 1 1 )
 ( ( 1 1 2 3 5 8 13 21 34 55 89 144 ) 144 89 55 34 21 13 8 5 3 2 1 1 )
 ( 1 1 2 3 5 8 13 21 34 55 89 144 ( 144 89 55 34 21 13 8 5 3 2 1 1 ) )
 ( 1 1 2 3 5 8 13 21 34 55 89 144 144 89 55 34 21 13 8 5 3 2 1 1 )
 ( 1 1 1 1 2 2 3 3 5 5 8 8 13 13 21 21 34 34 55 55 89 89 144 144 )
 ( 2 2 3 3 5 5 13 13 89 89 )
 ( 5 5 6 6 8 8 16 16 92 92 )
 254

when 'interpreted' with

$ clang++ -std=c++14 a.cpp && ./a.out

You can also use your favourite C++ compiler that supports the C++14 standard.

Here's the full code.

```
#include
#include

struct BoxBase
{
};

template
struct Box
: BoxBase
{
};

template
struct Unbox_;

template
struct Unbox_>
{
static constexpr int value = n;
};

template
constexpr int unbox = Unbox_::value;

struct ListBase
{
};

template
struct List
: ListBase
{
};

template<>
struct List<>
{
};

template
struct Cons_;

template
struct Cons_>
{
typedef List Type;
};

template
using Cons = typename Cons_::Type;

template
struct Head_;

template
struct Head_>
{
typedef T Type;
};

template
using Head = typename Head_::Type;

template
struct Tail_;

template
struct Tail_>
{
typedef List Type;
};

template
using Tail = typename Tail_::Type;

template
struct Reverse_
{
typedef typename R

Don't Reinvent The Wheel

A lot of the metafunctions you wrote are unnecessary as they already exist. At best, this is just extra code you have to deal with. But also some of the choices you made make some of the code unnecessarily complicated. Take your BoxBase, Box, Unbox_. All of that can be replaced with std::integral_constant<>. Box is std::integral_constant, and unbox is T::value. It's just less code and easier to understand.

Also EnableIf exists as std::enable_if_t, and If is std::conditional_t.

Hierarchy

There is no reason forListBase and there is no reason for a specialization for List<> (which isn't a ListBase??). Even if you don't use integral_constant, there is no reason for BoxBase. It's just code that doesn't add value. List should just be:

template 
struct List {
    using type = List;
    static constexpr size_t size = sizeof...(Ts); 
};

Convention

Metaprogramming is hard. It's hard to write, it's hard to debug. That's why it's very important to have conventions. One convention is that the result of a metafunction is named type. Not Type. Stick to convention.

Also, stick to types. Types are first-class citizens in the template metaprogramming world. Values and template templates suck. They need specific handling code all over the place and they're much more trouble than they're worth.

Lastly, we have the concept of metafunction class. In the Boost.MPL world, this was something like:

struct metafunction_class {
    template 
    struct apply {
        typedef ??? type;
    };
};

With C++11, this can simply down to:

struct metafunction_class {
    template 
    using apply = ???;
};

If all your metafunction classes meet that model, they become easier to use. What I don't understand about your code is that you have multiple nested Applys. Why? This line:

typedef typename U::template Apply>::template Apply, U>::Type> Type;

Has too much going on, and the double-Apply doesn't help.

Don't Be Afraid of Overloading

Your print code is reliant on various substitution failures to get it to do what you want to do. That makes it brittle and hard to read. Just use overloading. It's muuuch easier. For instance:

template 
void printLine() {
    details::print(T{}); // these are empty types anyway
    std::cout << '\n';
}

with:

namespace details {
    // here's your "box"
    template 
    void print(std::integral_constant ) {
         std::cout 
    void print(List ) {
        std::cout << " (";
        using expander = int[];
        expander{0,
            (void(
                print(Ts{})
            ), 0)...
        };
        std::cout << " )";
    }
}

Prefer Variadics to Recursion

As the above print for lists should make clear, code that relies on variadic templates is more concise and easier to follow than code that relies on recursion. So do that whenever you can. As an example, we can write FibList like so:

template 
using FibList = typename FibListImpl>::type;

Which sets the stage for:

template 
struct FibNum
: std::integral_constant::value + FibNum::value>
{ };

template <>
struct FibNum : std::integral_constant
{ };

template <>
struct FibNum : std::integral_constant
{ };

template 
struct FibListImpl
{
    using type = List...>; // everything in one go!
};

And lastly, here's how I would write map:

template 
using Map = decltype(details::map_impl(L{}, Func{}));

With, (1) Func being a convential metafunction class (2) overloading instead of recursion and (3) using variadics:

namespace details {
    template 
    auto map_impl(List, Func )
    -> List...>;
}

How cool is that? Pretty cool.

StackExchange Code Review Q#104188, answer score: 5