1.1.3 — типы как алгебра1.1.3 — types as algebra

Алгебраические типы данных (ADT)Algebraic data types (ADT)

Составные типы называются «алгебраическими», потому что комбинируются двумя операциями, ведущими себя как умножение и сложение: произведение типов (все поля одновременно) и сумма типов (ровно один из вариантов). Дисциплина «make invalid states unrepresentable» превращает целые классы багов в ошибки компиляции.Composite types are called "algebraic" because they combine via two operations that behave like multiplication and addition: product types (all fields at once) and sum types (exactly one of several variants). The discipline of "making invalid states unrepresentable" turns entire classes of bugs into compile errors.

частый теоретический вопросcommon theory question фундамент, не привязан к языкуfoundational, language-agnostic

Что этоWhat it is

Тип-произведение (product type) хранит значения всех своих полей одновременно — количество возможных значений равно произведению количеств значений каждого поля. Обычный struct/record/tuple — это произведение: struct { bool a; u8 b; } имеет ровно 2 × 256 = 512 различных состояний.A product type holds values of all its fields simultaneously — the number of possible values equals the product of each field's value count. An ordinary struct/record/tuple is a product: struct { bool a; u8 b; } has exactly 2 × 256 = 512 distinct states.

Тип-сумма (sum type, discriminated/tagged union) хранит значение ровно одного из перечисленных вариантов — количество возможных состояний равно сумме количеств состояний каждого варианта, плюс тег, определяющий, какой вариант активен сейчас. Это принципиально отличается от C-style union, где какой вариант «на самом деле» записан — неизвестно рантайму, если не хранить тег вручную.A sum type (a discriminated/tagged union) holds a value of exactly one of its listed variants — the number of possible states is the sum of each variant's state count, plus a tag identifying which variant is currently active. This is fundamentally different from a C-style union, where which variant is "really" stored is unknown to the runtime unless a tag is tracked by hand.

Одна и та же идея на разных языкахThe same idea across languages

01

Rust enum — тип-сумма как гражданин первого классаRust enum — a sum type as a first-class citizen

Каждый вариант может нести собственные данные разного типа. Компилятор требует исчерпывающий match — забытый вариант не компилируется, а не падает в рантайме.Each variant can carry its own, differently-typed data. The compiler requires an exhaustive match — a forgotten variant is a compile error, not a runtime crash.

enum Shape {
    Circle { radius: f64 },
    Rectangle { w: f64, h: f64 },
    Triangle { a: f64, b: f64, c: f64 },
}

fn area(s: &Shape) -> f64 {
    match s {
        Shape::Circle { radius } => std::f64::consts::PI * radius * radius,
        Shape::Rectangle { w, h } => w * h,
        Shape::Triangle { a, b, c } => { /* формула ГеронаHeron's formula */ 0.0 }
        // пропущенный вариант — ошибка компиляции "non-exhaustive match"// a missing arm is a compile error: "non-exhaustive match"
    }
}
02

C++ std::variant — сумма поверх системы шаблоновC++ std::variant — a sum type on top of the template system

До C++17 суммы типов в C++ выражались только через union без встроенной проверки тега или через наследование с виртуальной диспетчеризацией. std::variant — типобезопасная тегированная сумма, std::visit — аналог exhaustive match, но исчерпываемость не проверяется компилятором так же строго, как в Rust: об этом заботится сам visitor через if constexpr-цепочки или overload-паттерн.Before C++17, sum types in C++ could only be expressed via a tagless union or via inheritance with dynamic dispatch. std::variant is a type-safe tagged sum, and std::visit is the closest analogue to exhaustive match — though exhaustiveness isn't enforced by the compiler as strictly as in Rust; it's up to the visitor itself, via if constexpr chains or the overload pattern.

using Shape = std::variant<Circle, Rectangle, Triangle>;

double area(const Shape& s) {
    return std::visit([](const auto& shape) { return shape.area(); }, s);
}
03

TypeScript discriminated union — структурная сумма без enumTypeScript discriminated unions — a structural sum without an enum keyword

TypeScript выражает суммы через объединение интерфейсов с общим литеральным полем-тегом (kind) — компилятор сужает тип внутри каждой ветки switch автоматически по значению тега, и never в default ловит непокрытые варианты статически.TypeScript expresses sums as a union of interfaces sharing a common literal tag field (kind) — the compiler automatically narrows the type inside each switch branch based on the tag's value, and a never in the default case statically catches unhandled variants.

type Shape =
  | { kind: "circle"; radius: number }
  | { kind: "rectangle"; w: number; h: number };

function area(s: Shape): number {
  switch (s.kind) {
    case "circle": return Math.PI * s.radius ** 2;
    case "rectangle": return s.w * s.h;
    default: const _exhaustive: never = s; return _exhaustive;
  }
}
04

Python — без нативных ADT, эмуляция через dataclass + UnionPython — no native ADT, emulated via dataclass + Union

Python не имеет тегированных сумм на уровне языка; ближайший идиоматичный аналог — Union из typing над несколькими @dataclass, с проверкой исчерпываемости только статическим анализатором (mypy/pyright), а не рантаймом. С Python 3.10 match с case по типу приближает синтаксис к Rust, но гарантии остаются на совести линтера, а не языка.Python has no tagged sums at the language level; the closest idiomatic analogue is a typing.Union over several @dataclass types, with exhaustiveness checked only by a static analyzer (mypy/pyright), never by the runtime. Since Python 3.10, structural match/case brings the syntax closer to Rust, but the guarantees remain the linter's responsibility, not the language's.

Зачем: make invalid states unrepresentableWhy: make invalid states unrepresentable

Классический пример — сетевой запрос с булевым флагом is_loading, опциональным data и опциональным error: комбинация трёх независимых полей допускает 2 × 2 × 2 = 8 состояний, из которых валидны только 3 (загрузка / успех с данными / ошибка). Остальные 5 — «одновременно загружается и есть данные», «есть и данные, и ошибка» — существуют только потому, что поля независимы, и требуют ручной защитной проверки в каждом месте использования.The classic example is a network request with a boolean is_loading, an optional data, and an optional error: the combination of three independent fields allows 2 × 2 × 2 = 8 states, of which only 3 are valid (loading / success with data / error). The other 5 — "loading and has data at the same time," "has both data and an error" — exist purely because the fields are independent, and require a manual defensive check everywhere the value is used.

Свёртка тех же трёх полей в тип-сумму снижает число возможных состояний ровно до 3 валидных — недействительная комбинация перестаёт быть представимой в принципе, а не просто «маловероятной»:Collapsing the same three fields into a sum type reduces the number of possible states to exactly the 3 valid ones — an invalid combination stops being representable at all, rather than merely "unlikely":

enum RequestState<T> {
    Loading,
    Success(T),
    Error(String),
}
// 3 состояния вместо 8 — недействимые комбинации не существуют как значения типа// 3 states instead of 8 — invalid combinations don't exist as values of the type

ГраблиGotchas

C union — не алгебраический тип-суммаA C union is not an algebraic sum type

У C-style union нет встроенного тега: рантайм понятия не имеет, какое поле было записано последним, и чтение «не того» поля — undefined behavior (кроме специально оговорённых случаев common initial sequence). Тег в C приходится хранить и синхронизировать вручную рядом с union — именно эту ручную работу автоматизируют Rust enum и C++ std::variant.A C-style union has no built-in tag: the runtime has no idea which field was written last, and reading the "wrong" one is undefined behavior (aside from the specifically carved-out common-initial-sequence case). In C, the tag has to be stored and kept in sync by hand next to the union — this exact manual work is what Rust enums and C++ std::variant automate.

«Умножение» типов растёт быстрее, чем кажетсяType "multiplication" grows faster than it looks

Каждое дополнительное булево поле в структуре удваивает число состояний. Структура из 5 независимых булевых флагов имеет 32 состояния — на практике почти всегда валидны только 2-3 комбинации, что служит прямым сигналом переписать флаги через sum type.Every additional boolean field in a struct doubles the number of states. A struct with 5 independent boolean flags has 32 states — in practice almost always only 2-3 combinations are ever valid, which is a direct signal to rewrite the flags as a sum type.

std::visit без строгой проверки исчерпываемостиstd::visit without a strict exhaustiveness check

В отличие от Rust, где новый вариант enum ломает компиляцию всех match до его обработки, добавление нового типа в C++ std::variant не гарантирует ошибку компиляции во всех overload-based visitor — если overload-набор написан не идеально (например, есть generic catch-all перегрузка), новый вариант молча попадёт в неё.Unlike Rust, where a new enum variant breaks compilation of every match that doesn't handle it, adding a new type to a C++ std::variant doesn't guarantee a compile error across every overload-based visitor — if the overload set isn't written perfectly (say, it has a generic catch-all overload), the new variant will silently fall into it.