Algebraic data types and class hierarchies: Haskell and C++
A value that is one of several things, a circle or a rectangle, a success or a failure, a left or a right, is the shape both languages are built around and express in opposite ways. C++ puts the cases in classes derived from a common base and reaches them through a virtual call. Haskell puts the cases in one data line and reaches them with pattern matching.
The two programs below compute the same report from the same two values. The interesting part is not the output, which is identical to the last digit, but what happens when the type grows: a new case, or a new operation. Each language makes one of those two cheap and the other one expensive, and each compiler has a different opinion about a case that nobody handled.
The task in C++
The base class declares what every shape can do and nothing else: a virtual destructor for the ownership, a name, and an area. Both are pure virtual, so a subclass that forgets one is an abstract type and cannot be created at all. The two subclasses hold their own data and override the two functions, and a vector of unique_ptr owns the objects so that the polymorphism does not need a raw pointer.
#include <cstdio>
#include <memory>
#include <string>
#include <vector>
class Shape {
public:
virtual ~Shape() = default;
virtual std::string name() const = 0;
virtual double area() const = 0;
};
class Circle : public Shape {
public:
explicit Circle(double radius) : radius_(radius) {}
std::string name() const override { return "circle"; }
double area() const override { return 3.141592653589793 * radius_ * radius_; }
private:
double radius_;
};
class Rect : public Shape {
public:
Rect(double width, double height) : width_(width), height_(height) {}
std::string name() const override { return "rect"; }
double area() const override { return width_ * height_; }
private:
double width_;
double height_;
};
double total(const std::vector<std::unique_ptr<Shape>>& shapes) {
double sum = 0.0;
for (const auto& shape : shapes) {
sum += shape->area();
}
return sum;
}
int main() {
std::vector<std::unique_ptr<Shape>> shapes;
shapes.push_back(std::make_unique<Circle>(1.0));
shapes.push_back(std::make_unique<Rect>(2.0, 3.0));
for (const auto& shape : shapes) {
std::printf("%s %.2f\n", shape->name().c_str(), shape->area());
}
std::printf("total %.2f\n", total(shapes));
}
The build with -Wall -Wextra prints nothing, which is what a clean C++ build looks like. The run walks the vector and makes one virtual call per shape:
g++ -std=c++23 -Wall -Wextra -O2 shapes.cpp -o shapes
./shapes; echo "status $?"
circle 3.14
rect 6.00
total 9.14
status 0
The same task in Haskell
One declaration, two constructors, and a value of the type is one constructor applied to its fields. There is no base class and no virtual table in the source: area and name are ordinary functions over the type, and the case is the dispatch. A Shape value is still a heap object at run time, so nothing here claims to be faster; what changes is where the cases are written down.
module Main (main) where
import Text.Printf (printf)
data Shape
= Circle Double
| Rect Double Double
area :: Shape -> Double
area shape =
case shape of
Circle radius -> pi * radius * radius
Rect width height -> width * height
name :: Shape -> String
name shape =
case shape of
Circle _ -> "circle"
Rect _ _ -> "rect"
total :: [Shape] -> Double
total shapes = sum (map area shapes)
main :: IO ()
main = do
let shapes = [Circle 1.0, Rect 2.0 3.0]
mapM_ (\shape -> printf "%s %.2f\n" (name shape) (area shape)) shapes
printf "total %.2f\n" (total shapes)
The printer uses Text.Printf with the same format string as the C++ program, so the two outputs can be compared line by line. mapM_ is the loop:
ghc -Wall -O1 -o shapes-hs shapes.hs
./shapes-hs; echo "status $?"
[1 of 2] Compiling Main ( shapes.hs, shapes.o )
[2 of 2] Linking shapes-hs
circle 3.14
rect 6.00
total 9.14
status 0
What differs and why
The output is the same on both sides, and the difference is in the direction of the extension. A sum type has a closed set of cases: the constructors are written in one place, and every function that matches on the type knows all of them. A class hierarchy is open: a class in another file can derive from the base and the functions that use it need no edit.
| Change | Haskell | C++ |
|---|---|---|
| a new case, a triangle | one constructor, and every match must handle it or the compiler warns | one new class, and nothing else changes |
| a new operation, a perimeter | one new function, no other code changes | a new virtual in the base, and every subclass must implement it |
| dispatch | a case, checked for exhaustiveness | a virtual call through the object |
| the visitor pattern | not needed, a match is already one | the encoding of a match over a closed hierarchy |
The right-hand column is where the visitor pattern comes from. A C++ program that wants to add an operation without editing every class writes a visitor with one visit overload per type, which is Haskell's match translated into double dispatch. The pattern is not a design taste: it is the cost of an open hierarchy when you need the closed side.
Both languages let a program be wrong in the same way: a case can be handled with the wrong answer. What they differ in is the case that is not handled at all, which is the subject of the last chapter.
The hole each compiler finds
The version that breaks is the one where the base class has a default implementation of area, here return 0.0, and a new shape does not override it. It compiles without a warning, and the report is silently wrong:
#include <cstdio>
#include <memory>
#include <string>
#include <vector>
class Shape {
public:
virtual ~Shape() = default;
virtual std::string name() const = 0;
virtual double area() const { return 0.0; }
};
class Circle : public Shape {
public:
explicit Circle(double radius) : radius_(radius) {}
std::string name() const override { return "circle"; }
double area() const override { return 3.141592653589793 * radius_ * radius_; }
private:
double radius_;
};
class Triangle : public Shape {
public:
Triangle(double base, double height) : base_(base), height_(height) {}
std::string name() const override { return "triangle"; }
private:
double base_;
double height_;
};
int main() {
std::vector<std::unique_ptr<Shape>> shapes;
shapes.push_back(std::make_unique<Circle>(1.0));
shapes.push_back(std::make_unique<Triangle>(2.0, 3.0));
for (const auto& shape : shapes) {
std::printf("%s %.2f\n", shape->name().c_str(), shape->area());
}
}
g++ -std=c++23 -Wall -Wextra -O2 hole.cpp -o hole
./hole; echo "status $?"
circle 3.14
triangle 0.00
status 0
The same mistake in Haskell is a new constructor and a case that forgot it. The program below also only ever builds circles and rectangles, so it runs and prints the right answers, and the compiler is the only thing that notices:
module Main (main) where
import Text.Printf (printf)
data Shape
= Circle Double
| Rect Double Double
| Triangle Double Double
area :: Shape -> Double
area shape =
case shape of
Circle radius -> pi * radius * radius
Rect width height -> width * height
main :: IO ()
main = do
let shapes = [Circle 1.0, Rect 2.0 3.0]
mapM_ (\shape -> printf "%.2f\n" (area shape)) shapes
ghc -Wall -O1 -o hole-hs Hole.hs
./hole-hs; echo "status $?"
[1 of 2] Compiling Main ( Hole.hs, Hole.o )
Hole.hs:8:7: warning: [GHC-40910] [-Wunused-top-binds]
Defined but not used: data constructor ‘Triangle’
|
8 | | Triangle Double Double
| ^^^^^^^^^^^^^^^^^^^^^^
Hole.hs:12:5: warning: [GHC-62161] [-Wincomplete-patterns]
Pattern match(es) are non-exhaustive
In a case alternative:
Patterns of type ‘Shape’ not matched: Triangle _ _
|
12 | case shape of
| ^^^^^^^^^^^^^...
[2 of 2] Linking hole-hs
3.14
6.00
status 0
Two warnings, and both matter. GHC-62161 says the match does not cover Triangle, which is the bug, and GHC-40910 says the constructor is never built anywhere, which is the same fact from the other side. Under -Werror the build would stop, and a program that passed a Triangle to that function would die at run time with a non-exhaustive pattern error instead of printing a zero.
C++ had the same chance and gave it away: a default implementation in the base class is a decision that every future subclass is correct until it says otherwise. The strict version, = 0, does catch the missing override, and the page on one change made in both shows that error. The lesson is not that C++ cannot check this; it is that the check is opt-in and Haskell's is the default.
The Haskell lesson behind the syntax is algebraic data types, and the next page in this set is Immutability and pure functions.
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