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

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

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

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

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

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

 data Bool = False | True

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

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

Реалізація

Мова Haskell

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

Мова Nemerle

У мові Nemerle існує ключове слово «variant», за допомогою якого можна описати алгебричний тип даних. Всі створені таким шляхом варіанти можна зіставити зі зразком через ключове слово «match».

Мова Haxe

У мові Haxe алгебричний тип даних реалізується за допомогою анонімних типів і перерахувань. У мові передбачено зіставлення із зразком, яке так само можна застосувати для роботи з алгебричним типом даних.

Див. також

• Конструктор типів
• Узагальнений алгебричний тип даних
• Декартів добуток
• Диз'юнктне об'єднання
• Тип-добуток

Посилання

• Algebraic data type / Free On-line Dictionary of Computing (англ.)
• Brent Yorgey, 2: Algebraic Data Types / School of Haskell. Starting with Haskell. Introduction to Haskell(англ.)
• Algebraic data type [Архівовано 3 жовтня 2015 у Wayback Machine.] / Haskell wiki (англ.)
• Роман Душкин, Алгебраические типы данных и их использование в программировании [Архівовано 4 березня 2016 у Wayback Machine.], «Практика функционального программирования» (ISSN 2075-8456) 2009 № 2