What is Algebraic Types in C++?

Sum types and product types in C++: composing data with std::variant, std::optional, and structs to make illegal states unrepresentable.

Which C++ standard introduced Algebraic Types?

Algebraic Types was introduced in C++17.

What is the difficulty level of Algebraic Types?

Algebraic Types is considered Intermediate-level C++ material.

Algebraic Types

Algebraic Typessince C++17

Algebraic types are composite types formed by two orthogonal operations: product (all fields present simultaneously, as in a struct) and sum (exactly one of several alternatives active at a time, as in std::variant), enabling the compiler to enforce exhaustive case analysis and eliminate illegal states.

Overview

Algebraic type theory names two fundamental ways to compose types:

Product types hold all members simultaneously. A struct Point { double x; double y; } has a state space equal to the Cartesian product of double × double. Every struct, class, and std::tuple is a product type.
Sum types hold exactly one of several alternatives at a time. The state space is the sum — the union — of the alternatives' state spaces. Also called discriminated unions or tagged unions.

C++ has always had raw union and struct, but neither composition primitive was type-safe. Raw union shares storage without tracking which member is active; accessing the wrong member is undefined behaviour. Struct boolean flags like bool has_value; T value; duplicate constraint enforcement across every callsite.

C++17 closed the gap with two vocabulary types:

std::variant<Ts...> — the general sum type. Exactly one alternative is active at all times. Access through the wrong type throws or returns null.
std::optional<T> — the degenerate sum: T or nothing. Semantically equivalent to std::variant<std::monostate, T> but with a purpose-built interface for nullable values.

C++23 adds std::expected<T, E>, which is morally std::variant<T, E> with monadic operations for chaining fallible computations without exceptions.

The central payoff: when you add an alternative to a variant and fail to handle it in a std::visit call, the program fails to compile. There is no silent runtime fallthrough.

Syntax

Product types

cpp

Godbolt

// Plain struct — always available
struct Point { double x; double y; };

// C++11: std::tuple for anonymous products
#include <tuple>
using RGB = std::tuple<uint8_t, uint8_t, uint8_t>;

// C++17: structured bindings decompose any product type
auto [r, g, b] = RGB{255, 128, 0};

Sum types with std::variant

cpp

Godbolt

#include <variant>  // C++17

using Number = std::variant<int, double, long long>;

Number n = 42;     // holds int
n = 3.14;          // now holds double; previous value is destroyed
n = 100LL;         // now holds long long

// Non-throwing index-based probe
if (auto* p = std::get_if<double>(&n))      // C++17 — returns nullptr on mismatch
    std::cout << "double: " << *p << '\n';

// Throwing type-based access
double d = std::get<double>(n);             // throws std::bad_variant_access if wrong

// Unambiguous construction — avoids implicit-conversion surprises
std::variant<long, double> v{std::in_place_type<long>, 1};   // C++17

Exhaustive dispatch with std::visit

cpp

Godbolt

// Overload helper — deduction guide implicit in C++20, explicit needed in C++17
template<class... Fs>
struct overloaded : Fs... { using Fs::operator()...; };
template<class... Fs> overloaded(Fs...) -> overloaded<Fs...>;  // C++17 deduction guide

Number result = 3.14;
std::visit(overloaded{
    [](int i)       { std::cout << "int: "    << i << '\n'; },
    [](double d)    { std::cout << "double: " << d << '\n'; },
    [](long long l) { std::cout << "ll: "     << l << '\n'; },
}, result);
// Missing an alternative → compile error, not a runtime bug

Examples

Expression tree (recursive sum type)

Recursive variants require indirection because Expr cannot contain itself directly.

cpp

Godbolt

#include <variant>
#include <memory>
#include <string>
#include <unordered_map>

struct Literal  { double value; };
struct Variable { std::string name; };
struct BinaryOp;

using Expr = std::variant<Literal, Variable, std::unique_ptr<BinaryOp>>;

struct BinaryOp {
    char op;
    Expr lhs;
    Expr rhs;
};

double eval(const Expr& e, const std::unordered_map<std::string, double>& env) {
    return std::visit(overloaded{
        [](const Literal& l)                     { return l.value; },
        [&](const Variable& v)                   { return env.at(v.name); },
        [&](const std::unique_ptr<BinaryOp>& b)  {
            double l = eval(b->lhs, env), r = eval(b->rhs, env);
            switch (b->op) {
                case '+': return l + r;
                case '-': return l - r;
                case '*': return l * r;
                case '/': return l / r;
                default:  return 0.0;
            }
        },
    }, e);
}

Every new node kind added to Expr forces an update to every std::visit call — the compiler tracks the obligation, not comments or docs.

State machine without sentinel values

cpp

Godbolt

struct Idle    {};
struct Running { std::string task_name; };
struct Failed  { std::string error; int code; };
struct Done    { int exit_code; };

using WorkerState = std::variant<Idle, Running, Failed, Done>;

void start(WorkerState& s, std::string task) {
    std::visit(overloaded{
        [&](Idle&)    { s = Running{std::move(task)}; },
        [](Running&)  { /* already active — no-op or throw */ },
        [](Failed&)   { s = Idle{}; },   // reset before retry
        [](Done&)     { s = Idle{}; },
    }, s);
}

bool terminal(const WorkerState& s) noexcept {
    return std::holds_alternative<Failed>(s)   // C++17
        || std::holds_alternative<Done>(s);
}

Contrast this with enum class State { Idle, Running, Failed, Done } plus a separate string error; int code: nothing prevents State::Idle while error is non-empty.

Result type without exceptions (C++17 approximation)

cpp

Godbolt

template<class T, class E>
using Result = std::variant<T, E>;

struct ParseError { std::string msg; int line; };

Result<double, ParseError> parse_number(std::string_view sv) {  // string_view: C++17
    char* end{};
    double v = std::strtod(sv.data(), &end);
    if (end == sv.data())
        return ParseError{"not a number", 0};
    return v;
}

auto r = parse_number("3.14");
if (auto* val = std::get_if<double>(&r))
    std::cout << "parsed: " << *val << '\n';
else if (auto* err = std::get_if<ParseError>(&r))
    std::cerr << "error on line " << err->line << ": " << err->msg << '\n';

In C++23, replace this pattern with std::expected<double, ParseError>. It provides and_then, transform, and or_else for monadic chaining without manual visiting.

Optional for nullable returns

cpp

Godbolt

#include <optional>  // C++17

std::optional<std::string> find_user(const Database& db, int id) {
    auto row = db.query_one("SELECT name FROM users WHERE id = ?", id);
    if (!row) return std::nullopt;
    return row->get<std::string>("name");
}

// At the callsite, the absence is explicit and enforced
if (auto name = find_user(db, 42))
    greet(*name);

// C++23: monadic interface avoids manual if-checks
auto upper = find_user(db, 42)
    .transform([](std::string s) {
        std::ranges::transform(s, s.begin(), ::toupper);
        return s;
    })
    .value_or("UNKNOWN");

`std::expected` monadic chaining (C++23)

std::expected<T, E> is C++23's first-class error-return type. Unlike the manual Result<T,E> alias above, it ships with four monadic adapters — and_then, transform, transform_error, and or_else — that let you chain fallible steps into a linear pipeline. Each adapter short-circuits: the moment any step produces an error, the rest of the chain is skipped and the error propagates unchanged.

cpp

Godbolt

// C++23
#include <expected>
#include <fstream>
#include <string>

struct ConfigError { std::string msg; };
struct Config      { std::string host; int port; };

// Each function in the pipeline returns std::expected<NextType, ConfigError>
std::expected<std::string, ConfigError> read_file(const std::string& path) {
    std::ifstream f(path);
    if (!f) return std::unexpected(ConfigError{"cannot open: " + path});
    return std::string(std::istreambuf_iterator<char>(f), {});
}

std::expected<Config, ConfigError> parse_toml(const std::string& text) {
    // Imagine a real TOML parser here
    if (text.empty()) return std::unexpected(ConfigError{"empty config"});
    return Config{"localhost", 8080};   // simplified
}

std::expected<Config, ConfigError> validate_config(Config cfg) {
    if (cfg.port <= 0 || cfg.port > 65535)
        return std::unexpected(ConfigError{"invalid port"});
    return cfg;
}

// The pipeline — reads like sequential imperative code, but short-circuits on error
Config load_config(const std::string& path) {
    return read_file(path)
        .and_then(parse_toml)             // called only if read_file succeeds
        .and_then(validate_config)        // called only if parse_toml succeeds
        .transform([](Config c) {         // cheap post-processing on the happy path
            c.host = "https://" + c.host;
            return c;
        })
        .transform_error([](ConfigError e) {  // annotate errors on the sad path
            e.msg = "[config] " + e.msg;
            return e;
        })
        .value_or(Config{"127.0.0.1", 80});   // fallback if any step failed
}

The equivalent manual style requires a cascade of early-return checks that obscure the happy path:

cpp

Godbolt

// C++17 manual style — identical semantics, more noise
Config load_config_manual(const std::string& path) {
    auto text = read_file(path);
    if (!text) return Config{"127.0.0.1", 80};

    auto cfg = parse_toml(*text);
    if (!cfg) return Config{"127.0.0.1", 80};

    auto validated = validate_config(*cfg);
    if (!validated) return Config{"127.0.0.1", 80};

    validated->host = "https://" + validated->host;
    return *validated;
}

The monadic form makes the data flow explicit and centralizes the fallback in one place. or_else complements and_then on the error path: it receives the error value and can recover, log, or remap it to a different error type.

Multi-variant `std::visit` (C++17)

std::visit accepts more than one variant. When given N variants, it invokes the visitor with one active value from each, effectively dispatching over the N-dimensional Cartesian product of their active alternatives. Every combination must be handled — the compiler enforces completeness over all N×M branches.

cpp

Godbolt

// C++17
#include <variant>

enum class OperationType { Add, Multiply };
struct DenseMatrix  { /* ... */ };
struct SparseMatrix { /* ... */ };

using Operation   = std::variant<OperationType>;  // simplified — real code: variant<Add,Mul,...>
using StorageType = std::variant<DenseMatrix, SparseMatrix>;

// More realistic example: dispatch on two independent variants simultaneously
struct AddOp      {};
struct MultiplyOp {};
using Op = std::variant<AddOp, MultiplyOp>;

void apply_matrix_op(const Op& op, const StorageType& storage) {
    std::visit(overloaded{
        // Branch (AddOp, DenseMatrix)
        [](const AddOp&,      const DenseMatrix&)  { /* dense add */    },
        // Branch (AddOp, SparseMatrix)
        [](const AddOp&,      const SparseMatrix&) { /* sparse add */   },
        // Branch (MultiplyOp, DenseMatrix)
        [](const MultiplyOp&, const DenseMatrix&)  { /* dense mul */    },
        // Branch (MultiplyOp, SparseMatrix)
        [](const MultiplyOp&, const SparseMatrix&) { /* sparse mul */   },
    }, op, storage);
    // Omitting any of the 4 branches → compile error
}

Multi-visitation requires an overload set that covers every combination. If the behavior is the same for several combinations, use a generic lambda or a catch-all overload to consolidate them. The overloaded helper resolves overloads in declaration order, so put more-specific overloads before catch-alls.

`std::variant` index and `std::get_if` patterns

Every std::variant tracks which alternative is active as a zero-based integer index. variant.index() returns that index at runtime; std::get_if<N>(&v) gives a pointer to the Nth alternative, or nullptr if a different alternative is active. This is particularly useful when the variant holds duplicate types — for example std::variant<int, int> — where type-based access is ambiguous.

cpp

Godbolt

// C++17
#include <variant>
#include <iostream>

using IntPair = std::variant<int, int>;  // two ints; type-based get is ambiguous

IntPair v{std::in_place_index<0>, 42};  // first int

std::cout << v.index() << '\n';         // prints 0

// Index-based get_if — the only way to distinguish the two ints
if (auto* p = std::get_if<0>(&v))
    std::cout << "first int: "  << *p << '\n';
if (auto* p = std::get_if<1>(&v))
    std::cout << "second int: " << *p << '\n';

// A dispatch helper that converts a runtime index to a compile-time index
template<std::size_t I, class Variant, class Visitor>
decltype(auto) visit_index_impl(Variant&& var, Visitor&& vis) {
    if constexpr (I < std::variant_size_v<std::decay_t<Variant>>) {
        if (var.index() == I)
            return vis(std::integral_constant<std::size_t, I>{});
        return visit_index_impl<I + 1>(
            std::forward<Variant>(var), std::forward<Visitor>(vis));
    }
    __builtin_unreachable();
}

template<class Variant, class Visitor>
decltype(auto) visit_index(Variant&& var, Visitor&& vis) {
    return visit_index_impl<0>(
        std::forward<Variant>(var), std::forward<Visitor>(vis));
}

// Usage: receive the index as a compile-time constant
visit_index(v, [&]<std::size_t I>(std::integral_constant<std::size_t, I>) {
    std::cout << "active index at compile time: " << I << '\n';
    auto* p = std::get_if<I>(&v);
    // ...
});

Index-based access is also the safe fallback when type-based std::get_if<T> would be ambiguous due to repeated types. Prefer named alternatives (distinct wrapper types) over repeated raw types when the variant is part of a public interface.

`valueless_by_exception` recovery

A std::variant enters the valueless_by_exception state only in one narrow situation: an in-place construction or assignment attempt throws after the previously held value has already been destroyed. In that window the variant has no valid value. Any attempt to std::visit or std::get a valueless variant throws std::bad_variant_access.

cpp

Godbolt

// C++17
#include <variant>
#include <stdexcept>

struct Fragile {
    Fragile() = default;
    Fragile(int) { throw std::runtime_error{"construction failed"}; }
};

std::variant<std::string, Fragile> v{"hello"};

try {
    v.emplace<Fragile>(1);   // destroys the string, then throws → valueless
} catch (...) {}

if (v.valueless_by_exception()) {
    // Step 1: detect
    std::cerr << "variant is valueless — recovering\n";

    // Step 2: restore to a known-good alternative (emplace cannot throw for the first type here)
    v.emplace<std::string>("recovered");

    // Step 3: verify
    assert(!v.valueless_by_exception());
}

The best defence is to use alternatives whose constructors and move constructors are noexcept. Check with std::is_nothrow_move_constructible_v<T>. When that is not possible, a RAII guard can save and restore variant state around potentially throwing operations:

cpp

Godbolt

// C++17 — RAII guard that restores variant state on exception
template<class Variant>
class variant_guard {
    Variant& ref_;
    Variant  saved_;
public:
    explicit variant_guard(Variant& v) : ref_(v), saved_(v) {}

    ~variant_guard() noexcept {
        if (ref_.valueless_by_exception())
            ref_ = std::move(saved_);   // restore saved state
    }

    // Commit: caller calls this to discard the saved copy on success
    void commit() noexcept { saved_ = ref_; }
};

// Usage
std::variant<std::string, Fragile> v2{"initial"};
{
    variant_guard guard{v2};
    try {
        v2.emplace<Fragile>(1);  // may throw
        guard.commit();          // only reached if emplace succeeded
    } catch (...) {
        // guard destructor fires here, restoring v2 to "initial"
    }
}
assert(std::holds_alternative<std::string>(v2));

Prefer noexcept move constructors on all variant alternatives. When every alternative's move constructor is noexcept, std::variant's assignment operators use a double-buffering strategy internally that guarantees the valueless state is never reached.

`sizeof` and layout characteristics

std::variant stores all alternatives in a shared buffer sized for the largest alternative, plus a discriminant tag (typically an integer). The overhead means sizeof(std::variant<T...>) is always larger than max(sizeof(T)...).

cpp

Godbolt

// C++17 — layout exploration
#include <variant>
#include <optional>
#include <utility>   // std::pair
#include <iostream>

// Discriminant adds overhead beyond the largest member
static_assert(sizeof(std::variant<int, double>) > sizeof(double));

// std::optional<T> is typically sizeof(T) + alignment padding for the bool flag
// std::pair<bool, int> is similarly sizeof(int) + 1 byte bool + padding
// In most implementations: sizeof(optional<int>) == sizeof(pair<bool,int>) == 8

std::cout
    << "variant<int,double>  : " << sizeof(std::variant<int,double>)   << '\n'
    << "optional<int>        : " << sizeof(std::optional<int>)         << '\n'
    << "pair<bool,int>       : " << sizeof(std::pair<bool,int>)        << '\n'
    << "variant<monostate,int>: " << sizeof(std::variant<std::monostate,int>) << '\n';

// Typical output (x86-64, libstdc++):
//   variant<int,double>   : 16
//   optional<int>         : 8
//   pair<bool,int>        : 8
//   variant<monostate,int>: 8

// NOTE: std::variant<std::monostate, T> and std::optional<T> have different sizes
// in most implementations even though they model the same concept.
// std::optional is heavily optimized for the nullable-value use case.

Alignment also matters: if alternatives have different alignment requirements, the variant buffer is aligned to the strictest requirement and the remaining space is padded. A std::variant<char, double> wastes 7 bytes of padding before the double slot even though char only needs 1.

Prefer std::optional<T> over std::variant<std::monostate, T> for the nullable-value pattern. They model the same concept, but optional has a smaller footprint, a cleaner API (value_or, transform, and_then), and avoids the discriminant overhead of the general variant machinery.

Real-world patterns: JSON and AST

Variants shine whenever a domain type is genuinely open-ended. Two of the most common patterns are recursive data formats (JSON, XML) and query/expression DSLs (SQL, filter predicates).

JSON value type

A JSON value is exactly a sum type: null, boolean, integer, float, string, array, or object. The array and object cases are recursive — a JSON array is a list of JSON values — so they require pointer indirection to break the infinite size cycle.

cpp

Godbolt

// C++17 — forward declarations break the recursive size cycle
#include <variant>
#include <string>
#include <vector>
#include <map>
#include <memory>

struct JsonArray;
struct JsonObject;

// unique_ptr provides indirection; the incomplete types are filled in below
using Json = std::variant<
    std::monostate,                      // null
    bool,
    int64_t,
    double,
    std::string,
    std::unique_ptr<JsonArray>,
    std::unique_ptr<JsonObject>
>;

struct JsonArray  { std::vector<Json> elements; };
struct JsonObject { std::map<std::string, Json> members; };

// Serialise any Json value to a string
std::string to_string(const Json& j) {
    return std::visit(overloaded{
        [](std::monostate)                          { return std::string("null"); },
        [](bool b)                                  { return std::string(b ? "true" : "false"); },
        [](int64_t n)                               { return std::to_string(n); },
        [](double d)                                { return std::to_string(d); },
        [](const std::string& s)                    { return '"' + s + '"'; },
        [](const std::unique_ptr<JsonArray>& a)  {
            std::string out = "[";
            for (auto& e : a->elements) out += to_string(e) + ',';
            if (!a->elements.empty()) out.pop_back();
            return out + ']';
        },
        [](const std::unique_ptr<JsonObject>& o) {
            std::string out = "{";
            for (auto& [k, v] : o->members)
                out += '"' + k + "\":" + to_string(v) + ',';
            if (!o->members.empty()) out.pop_back();
            return out + '}';
        },
    }, j);
}

The std::unique_ptr indirection means JsonArray and JsonObject can remain incomplete at the point of the using Json = ... declaration. This is the standard pattern for any self-referential variant.

SQL expression type for an ORM query builder

A SQL expression AST is another naturally variant-shaped type: a column reference, a literal value, a binary operation, or a function call. The variant enforces that every query builder operator handles all expression kinds.

cpp

Godbolt

// C++17 — SQL expression variant for a lightweight ORM
#include <variant>
#include <string>
#include <vector>
#include <memory>

struct Column      { std::string table; std::string name; };
struct Literal     { std::string value; };  // already SQL-escaped
struct BinaryExpr;
struct FunctionCall;

using SqlExpr = std::variant<
    Column,
    Literal,
    std::unique_ptr<BinaryExpr>,
    std::unique_ptr<FunctionCall>
>;

struct BinaryExpr {
    std::string op;    // "=", "<", "AND", "OR", ...
    SqlExpr     lhs;
    SqlExpr     rhs;
};

struct FunctionCall {
    std::string          name;   // "COUNT", "COALESCE", ...
    std::vector<SqlExpr> args;
};

// Render any SqlExpr node to a SQL fragment
std::string render(const SqlExpr& expr);

std::string render(const SqlExpr& expr) {
    return std::visit(overloaded{
        [](const Column& c) {
            return c.table + '.' + c.name;
        },
        [](const Literal& l) {
            return l.value;
        },
        [](const std::unique_ptr<BinaryExpr>& b) {
            return '(' + render(b->lhs) + ' ' + b->op + ' ' + render(b->rhs) + ')';
        },
        [](const std::unique_ptr<FunctionCall>& f) {
            std::string out = f->name + '(';
            for (std::size_t i = 0; i < f->args.size(); ++i) {
                if (i) out += ", ";
                out += render(f->args[i]);
            }
            return out + ')';
        },
    }, expr);
}

// Builder usage
SqlExpr where_clause =
    std::make_unique<BinaryExpr>(BinaryExpr{
        "AND",
        std::make_unique<BinaryExpr>(BinaryExpr{
            "=", Column{"users","role"}, Literal{"'admin'"}}),
        std::make_unique<BinaryExpr>(BinaryExpr{
            ">", Column{"users","age"},  Literal{"18"}}),
    });
// render(where_clause) → "(users.role = 'admin' AND users.age > 18)"

When a new SQL node kind is added to SqlExpr, every render call that lacks a branch for it will fail to compile. The variant acts as a checked extension point: you cannot forget to handle a new case.

Best Practices

Prefer std::get_if over std::get when the alternative might legitimately be absent. std::get<T> throws std::bad_variant_access on mismatch; std::get_if<T> returns a nullable pointer. In hot paths, the pointer form avoids exception overhead.

Use std::monostate to opt into default construction. A std::variant<A, B> default-constructs to A{}. If A is not default-constructible, the variant is also not default-constructible. Prepend std::monostate to allow it: std::variant<std::monostate, NonDefault>.

Flatten nested variants. std::variant<A, std::variant<B, C>> is rarely correct. Flatten it to std::variant<A, B, C> to keep visit calls manageable and avoid double-dispatch.

Annotate visitor return types explicitly when alternatives differ. std::visit requires all branches to return the same type. If branches return int and long, the lambda deduces conflicting types. Annotate the return: [](int i) -> long { return i; } or wrap in an explicit cast.

Prefer std::optional<T> over std::variant<std::monostate, T> for the nullable-value pattern. They model the same concept but optional has a smaller footprint, a cleaner API, and is semantically clearer at callsites.

Use std::expected (C++23) instead of hand-rolled Result<T,E> variants. The monadic adapters (and_then, transform, or_else) are already implemented, well-specified, and composable; reimplementing them from scratch invites subtle bugs in the short-circuit logic.

Common Pitfalls

Valueless-by-exception state. If an alternative's move constructor throws during emplace, the variant enters a valueless_by_exception() state. Subsequent std::get calls throw. Avoid this by preferring alternatives whose move constructors are noexcept — check with std::is_nothrow_move_constructible_v<T> (C++17).

Ambiguous implicit conversions. std::variant<int, long> v = 1; may fail to compile or pick an unexpected alternative depending on overload resolution. Use std::in_place_type<T> for unambiguous construction, especially with arithmetic types.

std::optional<bool> boolean traps. An empty optional<bool> is falsy; a optional<bool> holding false is truthy. The idiomatic conversion to bool breaks intuition when T is itself bool, pointer, or another contextually-convertible type. Always use .has_value() and dereference separately rather than relying on bare boolean conversion.

Recursive types need indirection. A std::variant cannot list itself as an alternative; the size would be infinite. Introduce std::unique_ptr<Node> or std::shared_ptr<Node> as the recursive branch, as shown in the AST example above.

Multi-visitation scales as N×M. Visiting two variants with N and M alternatives respectively requires handling all N*M combinations. Adding one alternative to either variant adds an entire row or column of new required branches. Keep variants small when they will be used in multi-visitation.

transform vs and_then on std::expected. transform wraps its return value in std::expected automatically, while and_then requires the callback to return std::expected itself. Mixing them up produces a doubly-wrapped std::expected<std::expected<T,E>,E>, which rarely compiles as intended.