Тип-сума

Тип-сума (англ. tagged union) — це структура даних, що зберігає значення, що може належати до одного з декількох наперед визначених типів. Лише один із типів може використовуватися одночасно, а поле тегу (англ. tag) чітко вказує, який саме тип використовується. Його можна розглядати як тип, що має кілька “варіантів”, кожен з яких має оброблятися правильно під час маніпуляцій з цим типом.

Типи-суми є важливим елементом функційного програмування, де вони можуть комбінуватися із типами-добутками, утворюючи алгебраїчні типи даних (англ. ADT). У мовах програмуваннях, таких як Haskell або Rust, компілятор перевіряє, чи всі випадки типу-суми завжди обробляються, уникаючи цим багатьох типів помилок. Проте такі типи можуть бути реалізовані і в інших мовах програмування: в об’єктно-орієнтованому програмуванні аналогом типів-сум є запечатані класи.

Разом із поняттям “тип-сума” використовується поняття “конструктора”, що має схоже значення, що і в ООП, проте частково відрізняється. Конструктор типу-суми — це функція, що повертає значення типу-суми, враховуючи тег і значення відповідного типу. Наприклад,

data MyType = A Int | B

Це тип MyType, в якому конструктор A — це функція 1 аргумента типу Int, що повертає значення типу MyType, а конструктор B — функція 0 аргументів. Окремим випадком є “тип-перелік”, що являє собою тип-суму одиничних типів та відповідає множині конструкторів нульової арності, що не несуть в собі ніякої додаткової інформації окрім значення тегу.

Математично, типи-суми відповідають диз’юнктивним об’єднанням, що зазвичай записуються з використанням ${\textstyle +}$. Якщо дано елемент диз’юнктивного об’єднання ${\textstyle A+B}$, можна визначити, чи походить він з ${\textstyle A}$, чи з ${\textstyle B}$. Якщо елемент знаходиться в обох множинах, то в ${\textstyle A+B}$ існуватимуть дві фактично різні копії значення, одна в ${\textstyle A}$ і одна в ${\textstyle B}$. У теорії типів, тип-сума ${\textstyle A+B}$ має дві ін’єкції:

$${\displaystyle {\begin{aligned}&{\text{inj}}_{1}\colon A\rightarrow A+B,\\&{\text{inj}}_{2}\colon B\rightarrow A+B.\end{aligned}}}$$

Форма усунення (спосіб використання значень цього типу) в даному випадку є “аналізом випадків”, відома також як pattern matching у функційних мовах, таких як Haskell:

$${\displaystyle {\begin{aligned}&{\text{якщо }}e\colon A+B,\\&\quad e_{1}\colon \tau \ {\text{ при }}(x:A),\\&\quad e_{2}\colon \tau \ {\text{ при }}(y:B),\\&{\text{тоді }}{\mathsf {case}}\ e\ {\mathsf {of}}\ {\begin{cases}x\Rightarrow e_{1}\\y\Rightarrow e_{2}\end{cases}}\colon \tau \end{aligned}}}$$

Типи-суми забезпечують безпечний доступ до даних: компілятор перевіряє, який варіант типу є активним, і перевіряє, чи всі альтернативи оброблені. Вони також зменшують вимоги до пам’яті, зазвичай виділяючи місце лише для найбільшого значення.

Їхнім головним недоліком є додаткова пам’ять, необхідна для зберігання тегу, хоча вона зазвичай невелика (кілька бітів). У низькорівневих системах іноді використовуються обчислювані або згорнуті теги, щоб уникнути цих витрат. На відміну від нетегованих об’єднань типи-суми не призначені для реінтерпретації даних на бітовому рівні.

Типи-суми можуть також використовуватися для обробки “виняткових значень”, на кшталт опціональних типів або обробки винятків. Таке використання типів-сум можна формалізувати у вигляді монади:

$${\displaystyle {\begin{aligned}{\text{return}}\colon &A\to (A+E)=a\mapsto \operatorname {value} a,\\[1ex]{\text{bind}}\colon &(A+E)\to (A\to (B+E))\to (B+E)=\\&\qquad =a\mapsto f\mapsto {\begin{cases}\operatorname {err} e,&{\text{якщо }}a=\operatorname {err} e,\\f\,a',&{\text{якщо }}a=\operatorname {value} a'.\end{cases}}\end{aligned}}}$$

Скажімо, ми хочемо побудувати двійкове дерево цілих чисел. У Haskell ми б зробили це, створивши такий тип даних:

data Tree = Leaf Int | Node Tree Tree

Це тип-сума, що містить два випадки: листок (Leaf), що містить число, і вузол (Node), що містить в собі два підвузли, які в свою чергу можуть бути як Leaf, так і Node. Leaf та Node — це конструктори, які дозволяють нам фактично створювати довільні дерева, наприклад:

Node
    (Node (Leaf 1) (Leaf 2))
    (Node (Leaf 3) (Node (Leaf 4) (Leaf 5)))

що відповідає даному дереву:

• Алгебраїчні типи даних
• Тип-добуток
• Теорія типів
• Функційне програмування

• boost::variant — typesafe реалізація типу-суми в C++;C
• std.variant — реалізація в D 2.0.