Haskell typeclasses in C++

Haskell’s typeclasses are somewhat akin to what object oriented languages call interfaces or abstract classes: they define a “contract”, sometimes offer a default implementation, and even share some common vocabulary: a type that is an instance of a typeclass is said to be “deriving” it.

However, amongst the many differences, one stands out: while one can implement a typeclass for an existing type without modifying it, a class in most object oriented languages has to explicitly declare which interfaces it implements. A language that is a notable exception to this rule is Go. But in C++, which doesn’t have interfaces but only abstract classes, such a feat is impossible.

While developing my MCL library, I chose to represent color transformations as endomorphisms. It led me to implement an equivalent of Haskell’s mconcat function, to compress a list of transformations into one. Wanting that code to remain generic, I had to find a way, in C++, to describe monoids, and therefore typeclasses, which is the reason why I started, as usual, a side project.

The code that emerged from this little experiment is on Github, this post is about the journey. In case you doubted it: this is not something you’re really advised to do. Don’t try this at home. Except for fun. Fun is good.

Partial specialization

Let’s start with Monoid, which was my starting point. What’s a monoid anyway? Well, briefly, it’s a set (in the mathematical sense) equipped with an associative binary function and its neutral element. As far as Haskell is concerned, it’s expressed this way:

class Monoid a where
    mempty :: a
    mappend :: a -> a -> a

How should we translate that in C++? The naive first approach is to simply use (template) functions that we redefine for each type that we want to make an instance of our typeclass. We have two strategies from which we can choose when redefining functions: specialization and overloading. If we choose to specialize our functions, we have to create an alternate definition of our function with explicit type parameters; the compiler will know that both are only one function, with different implementations. Overloading, in contrast, consists in creating a brand new function with the same name but a different signature.

template <typename A>
using Endomorphism = std::function<A(A)>;

template <typename A>
A mempty();

template <typename A>
A mappend(A const&, A const&);

template <typename A>
Endomorphism<A> mempty<Endomorphism<A>>()
{
  return id<A>;
}

template <typename A>
Endomorphism<A> mappend<Endomorphism<A>>(Endomorphism<A> f,
                                         Endomorphism<A> g)
{
  return compose(f, g);
}

But alas, none of this can work. Partial specialization of functions isn’t allowed by the language, and overloading is not worth trying, at it will obviously only result in insolvable ambiguous function calls…

Which means we have no choice but to move to traits!

Traits

Traits are a useful tool while dealing with generic C++ template code. They’re metaprogramming functions over types: they’re template structs that map their parameter types to stuff: other types, functions, constants… And since they’re implemented with structs, they can be partially specialized, which is exactly what we need here. So, if we move everything in a Monoid class and partially specialize it…

template <typename A>
class Monoid
{
  public:
    static A empty();
    static A append(A, A);
};

template <typename A>
class Monoid<Endomorphism<A>>
{
  public:
    static Endomorphism<A> empty()
    {
      return id;
    }

    static Endomorphism<A> append(Endomorphism<A> f, Endomorphism<A> g)
    {
      return compose(f, g);
    }
};

This works wonders! For convenience, we only have to define two helper functions outside of the Monoid class, and voilà. Those two can be easily inlined and only provide syntaxic sugar.

template <typename A>
A empty()
{
  return Monoid<A>::empty();
}

template <typename A>
A append(A x, A y)
{
  return Monoid<A>::append(x, y);
}

But this solution isn’t a silver bullet… When trying to apply the same strategy to Functor, we encounter a new problem. -

Too much kindness

The issue is that, in Haskell, Functor isn’t defined over what we would call a concrete type (of kind *), but on a parameterized type (of kind * -> *). Trying to mimick this in C++ yields a new bunch of issues.

template <typename A>
using Vec = std::vector<A>;

template <template<typename> class F>
class Functor
{
  public:
    template <typename A, typename B>
    static F<B> fmap(std::function<B(A)>, F<A>);
};

template <>
class Functor<Vec>
{
  public:
    template <typename A, typename B>
    static Vec<B> fmap(std::function<B(A)>, Vec<A>)
    {
      // left as an uninteresting exercise to the reader. :)
    }
};

template <template<typename> class F, typename A, typename B>
F<B> fmap(std::function<B(A)> f, F<A> fa)
{
  return Functor<F>::template fmap<A, B>(f, fa);
}

The first issue is that almost all STL containers have more than one template parameter: vector for instances has two, which means we can’t specialize Functor with it, as Functor expects types with only one template parameter. This seems to be avoidable thanks to C++11 template type synonyms, such as the introduced Vec. However, the compiler has a hard time resolving our types with such shenanigans, because alias templates are never used in template template argument detection, which means that we have to call fmap with a fully explicit F parameter, as in fmap<Vec>(f, v).

This might seem acceptable, albeit ugly, until we move to Monad. Because, for Monad, we will want to override the >> and >>= operators. And we can’t really specify explicit parameters on operators… This means we have to choose between painfully writing verbose wrappers for all classes that don’t have the appropriate “kindness” (standard containers, Either…) or going back to the drawing board and find a new way to declare Functor and Monad…

Going full template

How can we make sure the compiler will resolve our types correctly while still making it easy to implement said typeclasses? Our only remaining option: using concrete types in template specialization. Monad should not be specialized over Vec but over Vec<A>. However, this requires a bit more information in the typeclass itself.

template <typename MA>
class Monad;

template <typename A>
class Monad<Vec<A>>
{
  public:
    typedef A Type;

    static Vec<A> mreturn(A a);

    template <typename B>
    static Vec<B> bind(Vec<A> as, std::function<Vec<B>(A)> f);
};

template <typename MA, // deduced from ma
          typename MB, // deduced from f
          typename A>  // deduced from f
MB operator >>= (MA ma, std::function<MB(A)> f)
{
  return Monad<MA>::bind(ma, f);
}

template <typename MA, // deduced from ma
          typename MB> // deduced from mb
MB operator >> (MA ma, MB mb)
{
  typedef typename Monad<MA>::Type A;
  std::function<MB(A)> f = [=](A){ return mb; };
  return ma >>= f;
}

The only downside, regarding the >>= operator, is that, since we’re deducing the types of MB and A from the type of f, we can’t use lambdas or function pointers with bind: we’re restricted to real instances of std::function. But at last, monads work as expected! The following snippet correctly outputs [0,1,2,3,4,5,6,7,8] (given a proper implementation of show).

int main()
{
  Vec<int> v = Vec<int> { 1, 4, 7 };
  std::function<Vec<int>(int)> f =
    [](int x){ return Vec<int> { x-1, x, x+1 }; };

  std::cout << show(v >>= f) << std::endl;
}

Wrapping up

You might have noticed that we didn’t give any common pattern for Monad. That’s because we can’t: there’s no generic way to extract either M or A from the given MA. But this isn’t a bad thing: this is the pattern that yields the best error messages. Trying, for instance, to call fmap on a random type A gives the following error in clang: implicit instantiation of undefined template 'Functor<A<int> >'.

And… this is it! A way to build haskell-like typeclasses in C++. You can find all the code of this article plus some extra on Github. Although some of those typeclasses might be useful in some very specific cases (Monoid comes to mind), the cataclysmic performance penalty of Functor or Monad over lists or vectors compared to handwritten code using standard C++ algorithms isn’t worth the lines it saves. It remains, however, a fun way to explore the internals and limits of C++’s type system.

What comes next, implementing the Cont monad for instance, is left as an exercise to the motivated reader. :)

Going further

While proofreading this article, I discovered the Functional C++ blog; they have a very similar way of implementing the Monoid typeclass. But they also do fun stuff with the STL containers. Worth the read!