Haskell typeclasses in C++2015-04-26
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.
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:
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.
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 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…
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.
But this solution isn’t a silver bullet… When trying to apply the same
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.
The first issue is that almost all STL containers have more than one
vector for instances has two, which means we can’t
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
This might seem acceptable, albeit ugly, until we move to
Monad. Because, for
Monad, we will want to override the
>>= 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
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.
not be specialized over
Vec but over
Vec<A>. However, this requires
a bit more information in the typeclass itself.
The only downside, regarding the
>>= operator, is that, since
we’re deducing the types of
A from the type of
f, we can’t
use lambdas or function pointers with
bind: we’re restricted to real
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
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
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
implicit instantiation of undefined template
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
Monad over lists or vectors compared to handwritten code
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. :)
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!