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

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

Простым примером алгебраического типа данных является список. Действительно, список имеет два конструктора — конструктор пустого списка и конструктор пары, первым элементом которой является значение определённого типа, а вторым — список. Пример определения списка на языке 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 Архивная копия от 2 октября 2015 на Wayback Machine / 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