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

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

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

data List a = Nil

| Cons a (List a)

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

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

data Bool = False | True

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

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

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

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