Алгебричний тип даних

Алгебричний тип даних — в інформатиці найзагальніший складений тип, який являє собою тип-суму з типів-добутків. Алгебричний тип має набір конструкторів, кожен з яких приймає на вхід значення певних типів і повертає значення конструйованого типу. Конструктор є функцією, яка будує значення свого типу на основі вхідних значень. Для подальшого видобування цих значень з алгебричного типу використовується зіставлення зі зразком.

Простим прикладом алгебричного типу даних є список. Дійсно, список має два конструктори — конструктор порожнього списку і конструктор пари, першим елементом якої є значення певного типу, а другим — список. Приклад визначення списку мовою Haskell:

 data List a = Nil 
       | Cons a (List a)

Так що видно, що алгебричні типи даних є контейнерними типами — вони містять у собі значення інших типів (або того ж самого типу). Те, що в списку перший конструктор не приймає на вхід ніяких параметрів, не повинно викликати сумніву. Така форма конструктора є необхідною для створення значень, які не містять нічого, але є «одиничними» елементами алгебричних типів даних.

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

 data Bool = False | True

Також алгебричний тип даних може бути абстрактним, якщо такий тип визначений у деякому модулі, з якого не експортуються конструктори відповідного типу, а доступ до значень всередині алгебричного типу даних здійснюється за допомогою спеціальних методів — селекторів. Особливо варто відзначити так звані «узагальнені алгебраїчні типи даних», реалізовані в мовах Haskell і ML.

Залишається відзначити, що з точки зору синтаксично-орієнтованого конструювання даних алгебричним типом даних є розмічене об'єднання декартових добутків типів. Кожний доданок у розміченому об'єднанні відповідає одному конструктору, а кожен конструктор своєю чергою визначає декартів добуток типів, відповідних параметрам конструктора. Конструктори без параметрів є порожніми добутками. Якщо алгебричний тип даних є рекурсивним, всі розмічені об'єднання обгортають рекурсивним типом, і кожен конструктор повертає рекурсивний тип.