Haskell typeclasses in C++
2015-04-26Haskell’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:
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
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
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.
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.
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
).
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!