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

Алгебраи́ческий тип да́нных — в теории программирования любой тип, значения которого являются значениями некоторых иных типов, «обёрнутыми» конструкторами алгебраического типа. Другими словами, алгебраический тип данных имеет набор конструкторов типа, каждый из которых принимает на вход значения определённых типов и возвращает значение конструируемого типа. Важное отличие конструктора типа от функции заключается в том, что конструктор не исполняется, но единственная его задача — создание значения своего типа на основе входных значений. Для работы с такими значениями используется механизм сопоставления с образцами, как наиболее эффективный способ разбора значений (но это не означает, что иные механизмы работы с значениями не применимы к алгебраическим типам данных).

Самым простым алгебраическим типом данных является список. Действительно, список имеет два конструктора — конструктор пустого списка и конструктор пары, первым элементом которой является значение определённого типа, а вторым — список. Пример определения списка на языке Haskell:

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

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

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

 data Bool = False | True

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

Остаётся отметить, что с точки зрения синтаксически-ориентированного конструирования данных алгебраическим типом данных является размеченное объединение декартовых произведений типов. Каждое слагаемое в размеченном объединении соответствует одному конструктору, а каждый конструктор в свою очередь определяет декартово произведение типов, соответствующих параметрам конструктора. Конструкторы без параметров являются пустыми произведениями. Если алгебраический тип данных является рекурсивным, всё размеченное объединение обёртывается рекурсивным типом, и каждый конструктор типа возвращает рекурсивный тип.

Реализация

Язык Haskell

В языке Haskell любой тип данных, который не является примитивным, является алгебраическим. Все возможные виды значений (перечисления, объекты, структуры и т. д.) строятся при помощи конструкторов алгебраических типов данных. Поэтому рассматриваемая тема является чрезвычайно важной для понимания системы типизации языка Haskell.

Язык Nemerle

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

См. также

• Обобщённый алгебраический тип данных
• Декартово произведение
• Размеченное объединение
• Синтаксически-ориентированное конструирование