Алгебраические типы: суммы и произведения

Откуда название «алгебраические»: типы складываются и умножаются, как числа, и это не метафора.

Алгебраический тип данных (ADT) — тип, построенный из произведений (всё сразу) и сумм (одно из) базовых типов.

Два способа собрать данные

Произведение — «и»: значение содержит несколько полей одновременно. Кортеж (Int, Bool), запись {x: Int, y: Int}, структура. Сумма — «или»: значение — это одна из нескольких альтернатив, помеченных тегом. Перечисление, вариант, Either, Maybe. Любой составной тип данных в типизированных языках собирается из этих двух конструкций.

-- произведение (Haskell-нотация)
data Point = Point Int Int            -- два поля СРАЗУ

-- сумма
data Shape = Circle Int               -- ЛИБО круг (радиус)
           | Rect Int Int             -- ЛИБО прямоугольник (стороны)

Почему «алгебраические»: считаем обитателей

Название буквально про арифметику. Число значений (обитателей) типа подчиняется правилам:

Тип	Число обитателей
`Bool`	2
`(Bool, Bool)` — произведение	2 × 2 = 4
`Either Bool Bool` — сумма	2 + 2 = 4
`Maybe Bool` = `Nothing \| Just Bool`	1 + 2 = 3
`Unit`	1 (единица умножения)
`Void`	0 (ноль сложения)

Произведение перемножает количества, сумма складывает. Unit ведёт себя как 1 ((Unit, T) по числу обитателей совпадает с T), Void — как 0. Эта алгебра реальна и предсказывает изоморфизмы типов.

Демонстрация: считаем обитателей программно

Зададим базовые размеры и правила суммы/произведения — и посчитаем число значений составных типов.

def prod(*sizes):
    r = 1
    for s in sizes: r *= s
    return r
def summ(*sizes):
    return sum(sizes)

Bool, Unit, Void = 2, 1, 0
print("(Bool, Bool)      :", prod(Bool, Bool))
print("Either Bool Bool  :", summ(Bool, Bool))
print("Maybe Bool        :", summ(Unit, Bool))      # Nothing | Just Bool
print("(Unit, Bool)      :", prod(Unit, Bool))      # = Bool
print("(Void, Bool)      :", prod(Void, Bool))      # = 0, обитателей нет

Вывод:

(Bool, Bool)      : 4
Either Bool Bool  : 4
Maybe Bool        : 3
(Unit, Bool)      : 2
(Void, Bool)      : 0

Заметьте (Void, Bool) = 0: чтобы построить пару, нужно значение Void, а его нет — значит, и пары нет. Алгебра типов не врёт.

Сопоставление с образцом

Суммы разбираются паттерн-матчингом: на каждый вариант — своя ветка. Сила типов в том, что компилятор проверяет исчерпывающность: забыли вариант — предупреждение или ошибка. Это превращает «не обработали случай» из рантайм-бага в ошибку компиляции — прямое продолжение идеи «illegal states unrepresentable».

area shape = case shape of
  Circle r   -> 3 * r * r
  Rect w h   -> w * h
  -- забудь ветку -- компилятор предупредит о неполноте

Как работает под капотом

В памяти сумма представляется тегом (какой это вариант) плюс полями этого варианта; произведение — просто полями подряд. Паттерн-матчинг компилируется в проверку тега и переход к нужной ветке. Анализ исчерпывности — это проверка, что ветки покрывают все теги; формально она опирается на ту же алгебру обитателей.

Частые ошибки

Эмулировать сумму через произведение с флагами и null. Это возвращает «недопустимые состояния»; настоящая сумма исключает их по типу.
Игнорировать предупреждение о неполном матчинге. Это и есть пойманный баг «забыли случай» — не глушите его.
Путать сумму и объединение (union) в духе C. Алгебраическая сумма тегирована: всегда известно, какой вариант активен.

Итоги

ADT строятся из произведений («и») и сумм («или»).
Число обитателей: произведение умножает, сумма складывает; Unit = 1, Void = 0.
Суммы разбираются паттерн-матчингом; компилятор проверяет исчерпывность.
Тегированная сумма исключает недопустимые состояния, в отличие от флагов и union.