Тип-сума (англ. tagged union) — це структура даних, що зберігає значення, що може належати до одного з декількох наперед визначених типів. Лише один із типів може використовуватися одночасно, а поле тегу (англ. tag) чітко вказує, який саме тип використовується. Його можна розглядати як тип, що має кілька “варіантів”, кожен з яких має оброблятися правильно під час маніпуляцій з цим типом.
Опис
Типи-суми є важливим елементом функційного програмування, де вони можуть комбінуватися із типами-добутками, утворюючи алгебраїчні типи даних (англ. ADT). У мовах програмуваннях, таких як Haskell або Rust, компілятор перевіряє, чи всі випадки типу-суми завжди обробляються, уникаючи цим багатьох типів помилок. Проте такі типи можуть бути реалізовані і в інших мовах програмування: в об’єктно-орієнтованому програмуванні аналогом типів-сум є запечатані класи.
Разом із поняттям “тип-сума” використовується поняття “конструктора”, що має схоже значення, що і в ООП, проте частково відрізняється. Конструктор типу-суми — це функція, що повертає значення типу-суми, враховуючи тег і значення відповідного типу. Наприклад,data MyType = A Int | BЦе тип MyType, в якому конструктор A — це функція 1 аргумента типу Int, що повертає значення типу MyType, а конструктор B — функція 0 аргументів. Окремим випадком є “тип-перелік”, що являє собою тип-суму та відповідає множині конструкторів нульової арності, що не несуть в собі ніякої додаткової інформації окрім значення тегу. Математичне значення
Математично, типи-суми відповідають диз’юнктивним об’єднанням, що зазвичай записуються з використанням . Якщо дано елемент диз’юнктивного об’єднання , можна визначити, чи походить він з , чи з . Якщо елемент знаходиться в обох множинах, то в існуватимуть дві фактично різні копії значення, одна в і одна в . У теорії типів, тип-сума має дві ін’єкції:
Форма усунення (спосіб використання значень цього типу) в даному випадку є “аналізом випадків”, відома також як pattern matching у функційних мовах, таких як Haskell:
Переваги та недоліки
Типи-суми забезпечують безпечний доступ до даних: компілятор перевіряє, який варіант типу є активним, і перевіряє, чи всі альтернативи оброблені. Вони також зменшують вимоги до пам’яті, зазвичай виділяючи місце лише для найбільшого значення.
Їхнім головним недоліком є додаткова пам’ять, необхідна для зберігання тегу, хоча вона зазвичай невелика (кілька бітів). У низькорівневих системах іноді використовуються обчислювані або згорнуті теги, щоб уникнути цих витрат. На відміну від нетегованих об’єднань типи-суми не призначені для реінтерпретації даних на бітовому рівні.
Типи-суми можуть також використовуватися для обробки “виняткових значень”, на кшталт опціональних типів або обробки винятків. Таке використання типів-сум можна формалізувати у вигляді монади:
Приклад
Скажімо, ми хочемо побудувати двійкове дерево цілих чисел. У 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.