Overview
9 Algebraic data types and pattern matching
This chapter motivates designing programs so that illegal or contradictory states are impossible to represent. It introduces algebraic data types as a practical way to model state and behavior in C++, using a simple word-counting example to show how replacing scattered flags with explicit states removes ambiguity, prevents runtime mistakes, and lets RAII automatically manage resources tied to particular states.
Product types (structs/tuples) combine values, while sum types represent alternatives. The chapter contrasts open sum types via inheritance with closed, type-safe sums via std::variant, highlighting that variants store values (not pointers), avoid dynamic allocation, and encode all possibilities in the type. It then presents std::optional as a specialized sum for “maybe” values and builds an expected
For domain modeling, the Tennis kata shows how to split the game into precise states (normal scoring, forty scoring, deuce, advantage) so invalid combinations cannot occur. To work ergonomically with these ADTs, the chapter advocates pattern matching: in standard C++ via std::visit plus overloaded callables for type-directed dispatch, and, for richer patterns, with libraries like Mach7. The result is exhaustive, compiler-checked handling of all cases and code that is safer, clearer, and easier to evolve.
Implementing sum types with inheritance is simple. You can create multiple classes that inherit a common state_t class, and the current state is denoted by a pointer pointing to an instance of one of these classes.
Variants can be used to define proper sum types. You get a value type that can contain a value of any of the summed types in its own memory space. The variant instance will be at least the size of the biggest type you’re summing, regardless of the value it currently holds.
When counting the number of words on a web page, you have three main states. Before you have the web page, you can’t do anything. When you get the web page, you can start counting. While counting, you need to store the current count and the handler to the web page. When the counting is finished, you no longer need the handle to the web page; you can just store the final count.
Summary
- Implementing program state through algebraic data types requires some thinking and produces longer code, but it allows you to minimize the number of states your program can be in and removes the possibility of having invalid states.
- Inheritance, dynamic dispatch, and the visitor pattern are often used in OO programming languages to implement sum types. The main problem with using inheritance to implement sum types is that it incurs runtime performance penalties.
- If you know exactly which types you want to sum, variants are a better choice for implementing sum types than inheritance. The main downside of
std::variantis that it incurs a lot of boilerplate because of thestd::visitfunction. - Unlike exceptions—which should denote, as their name indicates, exceptional situations a program can find itself in—optional values and the
expectedclass are perfect for explicitly stating the possibility of failures. They also travel across multiple threads and multiple processes more easily. - The idea of having a type that contains either a value or an error has been popular in the functional programming world for a long time. This concept became popular in the C++ community after Andrei Alexandrescu gave a talk called “Systematic Error Handling in C++” at a 2012 C++ and Beyond conference (http://mng.bz/q5XF), where he presented his version of the
expectedtype. That version ofexpectedwas similar to ours, but it supported onlystd::exception_ptras the error type.
FAQ
What are algebraic data types, and what do “sum” and “product” mean in C++?
- Product type: combines values of multiple types together. In C++, classes/structs, std::pair, and std::tuple are product types.
- Sum type: holds a value of one of several alternatives (mutually exclusive). In C++, enums, std::variant, and std::optional are sum types.
- Rule of thumb: use product types to say “and,” sum types to say “either/or.”
How do algebraic data types help remove invalid states?
- They model only valid combinations of data, making illegal states unrepresentable.
- Example: Replace separate flags like
started/finishedwith a sum type of states:init|running|finished. You can’t, for instance, be both running and finished. - Resources live only in the states that need them (e.g., a socket exists only in
running), so lifetimes are correct by construction.
How can I implement a sum type with inheritance versus std::variant?
- Inheritance (open sum):
- Base class (
state_t) + derived classes (init_t,running_t,finished_t). - Store a pointer to base, use virtuals/tags/casts to dispatch. - std::variant (closed sum):
-
std::variant<init_t, running_t, finished_t>stores the value directly (no heap by default).
When should I prefer std::variant over inheritance (and vice versa)?
- Prefer std::variant when: - The set of alternatives is fixed. - You want value semantics, no virtuals, and minimal boilerplate. - You want no dynamic allocation by default.
- Prefer inheritance when: - You need extensibility (plugins/new alternatives later). - Polymorphic behavior across an open set is required.
- Note:
std::anyoffers type-erased storage but is less efficient/expressive thanstd::variantfor closed sums.
How do I safely access or check the active alternative in std::variant?
std::get<T>(v): returnsT&or throwsstd::bad_variant_accessif not active.std::get_if<T>(&v): returnsT*ornullptrif not active.v.index(): returns the index of the active alternative.- Tip: Use
std::visitwith an overloaded visitor to avoid manual checking.
What is std::optional, and why is it better than using pointers for “maybe” values?
std::optional<T>is a sum type: “aTor no value.”- Advantages over raw pointers:
- Clear intent (no ownership confusion).
- Value semantics and RAII (no lifetime pitfalls).
- Expressive API:
has_value(),operator*,operator->. - Use pointers when denoting identity, polymorphism, or shared ownership; use
optionalfor absence/presence.
How can I model computations that may fail and still carry error details?
- Use a sum type like
expected<T, E>: either a valueTor an errorE. - Benefits over
optional: - Includes rich error info (code/message/exception_ptr). - Benefits over exceptions: - Makes failure explicit in the type and control flow.
- Implementation can be a tagged union or a thin wrapper around
std::variant<T, E>with a nicer API.
How do I model a domain (like tennis scoring) with ADTs to avoid illegal states?
- Decompose the domain into disjoint, meaningful states, each with only the data it needs:
-
normal_scoring(0/15/30 vs 0/15/30), -forty_scoring(leader at 40 vs other up to 30), -deuce, -advantage(who has it), - optionallygame_over. - Use
std::variantover these types to make 40–40 or mixed states unrepresentable by mistake.
How do I get pattern-matching-like behavior with std::variant in C++?
- Use
std::visitwith an “overloaded” visitor:template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; }; template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>; - Then:
std::visit(overloaded{ [](const normal_scoring&){ /* ... */ }, [](const forty_scoring&){ /* ... */ }, [](const deuce&){ /* ... */ }, [](const advantage&){ /* ... */ } }, state); - This emulates pattern matching by type with concise, type-safe dispatch.
What extra capabilities does the Mach7 library provide for pattern matching?
- Richer patterns than
std::visit: - Match on structure (deconstruction), specific values, and guards. - Write multiple cases that discriminate both by type and by field values. - Trade-offs: - Non-standard library, different (more verbose) syntax. - Useful when you need advanced matches beyond simple type-based dispatch.
What practical tips should I keep in mind when using ADTs and pattern matching in C++?
- Keep public APIs clear: avoid exposing raw tuples/pairs; prefer named structs.
- Localize variant access with visitors to keep code exhaustive and readable.
- Let states own only what they need; transitions naturally release resources.
- Choose closed sums (
variant) by default; use inheritance only when openness is required. - Use
optionalfor absence; useexpected(or similar) when you also need error details.
Functional Programming in C++ ebook for free
