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

Question

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<12>;
  using B = Reverse<A>;
  using C = Cons<A, B>;
  using D = Merge<A, List<B>>;
  using E = Merge<A, B>;
  using F = Sort<E>;
  using G = Filter<F, IsPrime>;
  using H = Map<G, Add::Apply<Box<3>>::template Apply>;
  using I = FoldRight<H, Add>;
  printLine<A>();
  printLine<B>();
  printLine<C>();
  printLine<D>();
  printLine<E>();
  printLine<F>();
  printLine<G>();
  printLine<H>();
  printLine<I>();
}

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 <iostream>
#include <type_traits>

struct BoxBase
{
};

template<int n>
struct Box
: BoxBase
{
};

template<typename T>
struct Unbox_;

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

template<typename T>
constexpr int unbox = Unbox_<T>::value;

struct ListBase
{
};

template<typename ...>
struct List
: ListBase
{
};

template<>
struct List<>
{
};

template<typename, typename>
struct Cons_;

template<typename T, typename ...Ts>
struct Cons_<T, List<Ts...>>
{
  typedef List<T, Ts...> Type;
};

template<typename T, typename U>
using Cons = typename Cons_<T, U>::Type;

template<typename>
struct Head_;

template<typename T, typename ...Ts>
struct Head_<List<T, Ts...>>
{
  typedef T Type;
};

template<typename T>
using Head = typename Head_<T>::Type;

template<typename>
struct Tail_;

template<typename T, typename ...Ts>
struct Tail_<List<T, Ts...>>
{
  typedef List<Ts...> Type;
};

template<typename T>
using Tail = typename Tail_<T>::Type;

template<typename T, typename U>
struct Reverse_
{
  typedef typename Reverse_<Tail<T>, Cons<Head<T>, U>>::Type Type;
};

template<typename T>
struct Reverse_<List<>, T>
{
  typedef T Type;
};

template<typename T>
using Reverse = typename Reverse_<T, List<>>::Type;

template<typename T, typename U>
struct Merge_
{
  typedef Cons<Head<T>, typename Merge_<Tail<T>, U>::Type> Type;
};

template<typename T>
struct Merge_<List<>, T>
{
  typedef T Type;
};

template<typename T, typename U>
using Merge = typename Merge_<T, U>::Type;

template<typename, typename T, typename>
struct If_
{
  typedef T Type;
};

template<typename T, typename U>
struct If_<Box<false>, T, U>
{
  typedef U Type;
};

template<typename T, typename U, typename V>
using If = typename If_<T, U, V>::Type;

template<typename T, template<typename> class U>
struct Filter_
{
  typedef If<U<Head<T>>, Cons<Head<T>, typename Filter_<Tail<T>, U>::Type>,
  typename Filter_<Tail<T>, U>::Type> Type;
};

template<template<typename> class T>
struct Filter_<List<>, T>
{
  typedef List<> Type;
};

template<typename T, template<typename> class U>
using Filter = typename Filter_<T, U>::Type;

template<template<typename, typename> class T>
struct Function2
{
  template<typename U>
  struct Apply_
  {
    template<typename V>
    using Apply = T<U, V>;
  };
  template<typename U>
  using Apply = Apply_<U>;
};

template<typename T>
struct Not2
{
  template<typename U>
  struct Apply_
  {
    template<typename V>
    using Apply = Box<!unbox<typename T::template Apply<U>::template Apply<V>>>;
  };
  template<typename U>
  using Apply = Apply_<U>;
};

template<typename T, typename U>
struct LessThan_2
{
  typedef Box<(unbox<T> > unbox<U>)> Type;
};

template<typename T, typename U>
using LessThan_ = typename LessThan_2<T, U>::Type;

using LessThan = Function2<LessThan_>;

template<typename T, typename U>
struct Add_2
{
  typedef Box<unbox<T> + unbox<U>> Type;
};

template<typename T, typename U>
using Add_ = typename Add_2<T, U>::Type;

using Add = Function2<Add_>;

template<typename T>
struct Sort_
{
  typedef Merge<typename Sort_<Filter<Tail<T>, LessThan::Apply<Head<T>>::template Apply>>::Type,
  Cons<Head<T>, typename Sort_<Filter<Tail<T>, Not2<LessThan>::template Apply<Head<T>>::template Apply>>::Type>> Type;
};

template<>
struct Sort_<List<>>
{
  typedef List<> Type;
};

template<typename T>
using Sort = typename Sort_<T>::Type;

template<bool b, typename T>
using EnableIf = typename std::enable_if<b, T>::type;

template<typename T, typename U>
constexpr bool isBaseOf = std::is_base_of<T, U>::value;

template<typename T>
EnableIf<isBaseOf<BoxBase, T>, void> print()
{
  std::cout << ' ' << unbox<T>;
}

template<typename T>
EnableIf<isBaseOf<List<>, T>, void> print_();

template<typename T>
EnableIf<isBaseOf<ListBase, T>, void> print_();

template<typename T>
EnableIf<isBaseOf<ListBase, T>, void> print()
{
  std::cout << " (";
  print<Head<T>>();
  print_<Tail<T>>();
  std::cout << " )";
}

template<typename T>
EnableIf<isBaseOf<List<>, T>, void> print_()
{
}

template<typename T>
EnableIf<isBaseOf<ListBase, T>, void> print_()
{
  print<Head<T>>();
  print_<Tail<T>>();
}

template<typename T>
void printLine()
{
  print<T>();
  std::cout << '\n';
}

template<int n>
struct Fib_
{
  static constexpr int value = Fib_<n - 1>::value + Fib_<n - 2>::value;
};

template<>
struct Fib_<0>
{
  static constexpr int value = 0;
};

template<>
struct Fib_<1>
{
  static constexpr int value = 1;
};

template<int n>
constexpr int fib = Fib_<n>::value;

template<int n>
struct FibList_
{
  typedef Cons<Box<fib<n>>, typename FibList_<n - 1>::Type> Type;
};

template<>
struct FibList_<0>
{
  typedef List<> Type;
};

template<int n>
using FibList = Reverse<typename FibList_<n>::Type>;

template<int n, int n2>
struct IsPrime_2
{
  typedef If<Box<n % n2 == 0>, Box<false>, typename IsPrime_2<n, n2 + 1>::Type> Type;
};

template<int n>
struct IsPrime_2<n, n>
{
  typedef Box<true> Type;
};

template<typename T>
struct IsPrime_
{
  typedef typename IsPrime_2<unbox<T>, 2>::Type Type;
};

template<>
struct IsPrime_<Box<1>>
{
  typedef Box<false> Type;
};

template<>
struct IsPrime_<Box<2>>
{
  typedef Box<true> Type;
};

template<typename T>
using IsPrime = typename IsPrime_<T>::Type;

template<typename T, template<typename> class U>
struct Map_
{
  typedef Cons<U<Head<T>>, typename Map_<Tail<T>, U>::Type> Type;
};

template<template<typename> class T>
struct Map_<List<>, T>
{
  typedef List<> Type;
};

template<typename T, template<typename> class U>
using Map = typename Map_<T, U>::Type;

template<typename T, typename U>
struct FoldRight_
{
  typedef typename U::template Apply<Head<T>>::template Apply<typename FoldRight_<Tail<T>, U>::Type> Type;
};

template<typename T, typename U>
struct FoldRight_<List<T>, U>
{
  typedef T Type;
};

template<typename T, typename U>
using FoldRight = typename FoldRight_<T, U>::Type;

int main()
{
  using A = FibList<12>;
  using B = Reverse<A>;
  using C = Cons<A, B>;
  using D = Merge<A, List<B>>;
  using E = Merge<A, B>;
  using F = Sort<E>;
  using G = Filter<F, IsPrime>;
  using H = Map<G, Add::Apply<Box<3>>::template Apply>;
  using I = FoldRight<H, Add>;
  printLine<A>();
  printLine<B>();
  printLine<C>();
  printLine<D>();
  printLine<E>();
  printLine<F>();
  printLine<G>();
  printLine<H>();
  printLine<I>();
}

live example

Barry · Accepted Answer · 2015-09-09 13:59:06Z

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<n>, Unbox_<T>. All of that can be replaced with std::integral_constant<>. Box<4> is std::integral_constant<int, 4>, and unbox<T> 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 <typename... Ts>
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<Head<T>>::template Apply<typename FoldRight_<Tail<T>, 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 <typename T>
void printLine() {
    details::print(T{}); // these are empty types anyway
    std::cout << '\n';
}

with:

namespace details {
    // here's your "box"
    template <typename T, T val>
    void print(std::integral_constant<T, val> ) {
         std::cout << ' ' << val;
    }

    // here's your "list"
    template <typeanme... Ts>
    void print(List<Ts...> ) {
        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 <int N>
using FibList = typename FibListImpl<std::make_integer_sequence<int, N>>::type;

Which sets the stage for:

template <int N>
struct FibNum
: std::integral_constant<size_t,
                         FibNum<N-1>::value + FibNum<N-2>::value>
{ };

template <>
struct FibNum<0> : std::integral_constant<size_t, 0>
{ };

template <>
struct FibNum<1> : std::integral_constant<size_t, 1>
{ };

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

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

template <typename L, typename Func>
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 <typename... Ts, typename Func>
    auto map_impl(List<Ts...>, Func )
    -> List<Func::template apply<Ts>...>;
}

How cool is that? Pretty cool.

About your "reinventing the wheel" part, I just reimplemented some of the metafunctions to make my code look a bit more consistent. That is, If and Box instead of std::conditional_t and std::integral_constant. I'll have a deeper look on your other comments later on. — user97096
– user97096, Commented Sep 9, 2015 at 14:09

Stack Exchange Network

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

1 Answer 1

You must log in to answer this question.

Hot Network Questions

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

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions