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

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

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

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

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

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

  data Bool = False | True

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

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