Type classes, templates and concepts: Haskell and C++

Both languages let one function serve several types without knowing them in advance, and both call it ad-hoc polymorphism. C++ does it with templates, which the compiler instantiates per type, and with concepts, which say what an argument must support. Haskell does it with type classes, which are a list of functions a type can be given, and an instance, which is the list for one type.

The two programs below describe a value and double it, for Int and for a string. They print the same four lines. The difference is where the decision is made and what happens when a type that should not be allowed gets in.

A template, an overload and a concept

describe is one template with an if constexpr on the type: a compile-time branch that the compiler throws away for the branch it does not take. That is a template doing the work of two overloads, and it is the C++20 way to write it without a helper class per type.

twice is a template with a concept. The concept is a requirement written as an expression: left + right must compile, or the template is not a candidate and the error names the concept instead of the instantiation.

#include <cstdio> #include <string> #include <type_traits> template <class T> std::string describe(const T& value) { if constexpr (std::is_integral_v<T>) { return "number " + std::to_string(value); } else { return "text " + value; } } template <class T> concept Addable = requires(T left, T right) { left + right; }; template <Addable T> T twice(T value) { return value + value; } int main() { std::printf("%s\n", describe(42).c_str()); std::printf("%s\n", describe(std::string("hi")).c_str()); std::printf("%d\n", twice(21)); std::printf("%s\n", twice(std::string("ab")).c_str()); }

g++ -std=c++23 -Wall -Wextra -O2 classes.cpp -o classes
./classes; echo "status $?"

number 42
text hi
42
abab
status 0

A class and two instances

A Haskell class declares the names and their types, and an instance gives them for one type. Addable also shows a default method: twice is written once in the class in terms of add, and an instance that only provides the addition gets the doubling for free.

module Main (main) where import Text.Printf (printf) class Describable a where describe :: a -> String instance Describable Int where describe value = "number " ++ show value instance Describable String where describe text = "text " ++ text class Addable a where add :: a -> a -> a twice :: a -> a twice value = add value value instance Addable Int where add = (+) instance Addable String where add = (++) main :: IO () main = do putStrLn (describe (42 :: Int)) putStrLn (describe "hi") printf "%d\n" (twice (21 :: Int)) putStrLn (twice "ab")

ghc -Wall -O1 -o classes-hs Classes.hs
./classes-hs; echo "status $?"

[1 of 2] Compiling Main             ( Classes.hs, Classes.o )
[2 of 2] Linking classes-hs
number 42
text hi
42
abab
status 0

Nominal against structural

A template is structural: any type that supports the operations the body uses is accepted, and the check happens when the template is instantiated for that type. A type class is nominal: a type is in the class because somebody wrote an instance, and there is no other way in. Two consequences follow, and both show up in ordinary code.

The first is where new things are cheap. A C++ program can call twice on a type from a library it cannot edit, as long as the type has +; that is structural polymorphism for free. A Haskell type needs an instance, and the instance belongs in the module that owns the class or the type; one written anywhere else is an orphan, which GHC reports with -Worphans, and that rule is what stops two libraries from defining the same instance differently.

The second is what the compiler emits. A template is instantiated per type, so a program that uses std::sort on ten types contains ten sorts; a type class is a dictionary passed to one copy of the function, unless the optimiser specialises it, which GHC does for known types. C++ pays in code size and gains in inlining; Haskell pays in indirection and can erase it again.

The concept is the closest C++ has to a class constraint, and the difference between them is the one in the name: a concept is a predicate on a type, checked where it is used, and it does not give the type any operations the type did not already have. An instance adds an operation: Addable is why a string can be twiced in Haskell at all, while a C++ string may always be added with + whether or not the author wanted it.

The argument that is too true

A concept checks that an expression compiles, not that its result means anything. bool has +: it is the arithmetic conversion to int, and true + true is 2. The template is happy, the return type is T, and twice(true) returns a bool:

#include <cstdio> #include <string> template <class T> concept Addable = requires(T left, T right) { left + right; }; template <Addable T> T twice(T value) { return value + value; } int main() { std::printf("%d\n", twice(21)); std::printf("%d\n", twice(true)); }

g++ -std=c++23 -Wall -Wextra -O2 boolean.cpp -o boolean
./boolean; echo "status $?"

42
1
status 0

The second line is 1, because the two became a bool again, and no warning was printed. The concept was satisfied and the answer is wrong, which is the honest limit of structural constraints: they know the syntax of a type, not its algebra.

Haskell refuses the same program before it runs, because Bool has no Describable instance and there is no structural rescue:

module Main (main) where class Describable a where describe :: a -> String instance Describable Int where describe value = "number " ++ show value main :: IO () main = putStrLn (describe True)

ghc -Wall -O1 -o noinstance-hs NoInstance.hs; echo "status $?"

[1 of 2] Compiling Main             ( NoInstance.hs, NoInstance.o )
NoInstance.hs:10:18: error: [GHC-39999]
    • No instance for ‘Describable Bool’
        arising from a use of ‘describe’
    • In the first argument of ‘putStrLn’, namely ‘(describe True)’
      In the expression: putStrLn (describe True)
      In an equation for ‘main’: main = putStrLn (describe True)
   |
10 | main = putStrLn (describe True)
   |                  ^^^^^^^^

status 1

GHC-39999 names the missing instance and the line that needs it. The trade is the one the previous chapter described: the Haskell compiler knows the set of types a class has, so it can say no; the C++ compiler knows the operations a type supports, so it says yes to a boolean that adds.

The Haskell lesson on classes is type classes, and the next page in this set is Maybe, Either and exceptions.

The C++ program was built with g++ 15.2.0 (Alpine 15.2.0) using -std=c++23 -Wall -Wextra -O2 and the Haskell program with GHC 9.10.3 using -Wall -O1, both run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev