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

В компьютерном программировании , особенно в функциональном программировании и теории типов , алгебраический тип данных - это своего рода составной тип , то есть тип, образованный путем объединения других типов.

Двумя общими классами алгебраических типов являются типы продуктов (т. Е. Кортежи и записи ) и типы сумм (т. Е. Помеченные или непересекающиеся союзы , типы копродуктов или типы вариантов ).

Эти значения такого типа продукта обычно содержат несколько значений, называемых полями . Все значения этого типа имеют одинаковую комбинацию типов полей. Множество всех возможных значений типа продукта - это теоретико-множественное произведение, т. Е. Декартово произведение множеств всех возможных значений его типов полей.

Значения типа суммы обычно группируются в несколько классов, называемых вариантами . Значение вариантного типа обычно создается с помощью квазифункционального объекта, называемого конструктором . У каждого варианта есть собственный конструктор, который принимает указанное количество аргументов с указанными типами. Множество всех возможных значений типа суммы является теоретико-множественной суммой, т. Е. Непересекающимся объединением множеств всех возможных значений ее вариантов. Перечислимые типы - это особый случай типов суммы, в которых конструкторы не принимают аргументов, поскольку для каждого конструктора определено ровно одно значение.

Значения алгебраических типов анализируются с помощью сопоставления с образцом , которое идентифицирует значение по его конструктору или именам полей и извлекает содержащиеся в нем данные.

Алгебраические типы данных были введены в Hope , небольшом функциональном языке программирования, разработанном в 1970-х годах в Эдинбургском университете .

Примеры

Одним из наиболее распространенных примеров алгебраического типа данных является односвязный список . Тип списка - это тип суммы с двумя вариантами: Nilдля пустого списка и для комбинации нового элемента x со списком xs для создания нового списка. Вот пример того, как односвязный список будет объявлен в Haskell : Cons x xs

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

Consэто аббревиатура от cons truct. Многие языки имеют специальный синтаксис для списков, определенных таким образом. Например, Haskell и ML использовать []для Nil, :или ::для Cons, соответственно, и квадратные скобки для целых списков. Так , Cons 1 (Cons 2 (Cons 3 Nil))как правило, записывается в виде 1:2:3:[]или [1,2,3]в Haskell, или как 1::2::3::[]или [1;2;3]в ML.

В несколько более сложном примере бинарные деревья могут быть реализованы в Haskell следующим образом:

data Tree = Empty
          | Leaf Int
          | Node Tree Tree

Здесь Emptyпредставляет собой пустое дерево, Leafсодержит фрагмент данных и Nodeорганизует данные по ветвям.

В большинстве языков, поддерживающих алгебраические типы данных, можно определять параметрические типы. Примеры приведены далее в этой статье.

В некоторой степени аналогично функции, конструктор данных применяется к аргументам соответствующего типа, в результате чего получается экземпляр типа данных, которому принадлежит конструктор типа. Например, конструктор данных Leafлогически является функцией Int -> Tree, что означает, что передача целого числа в качестве аргумента Leafдает значение типа Tree. Поскольку Nodeпринимает два аргумента самого типа Tree, тип данных является рекурсивным .

Операции с алгебраическими типами данных можно определить, используя сопоставление с образцом для извлечения аргументов. Например, рассмотрим функцию для определения глубины a Tree, приведенную здесь в Haskell:

 depth :: Tree -> Int
 depth Empty = 0
 depth (Leaf n) = 1
 depth (Node l r) = 1 + max (depth l) (depth r)

Таким образом, Treeданное to depthможет быть построено с использованием любого из Empty, Leafили, Nodeи должно быть сопоставлено с любым из них, соответственно, чтобы иметь дело со всеми случаями. В случае Node, шаблон извлекает поддеревья lи rдля дальнейшей обработки.

Алгебраические типы данных хорошо подходят для реализации абстрактного синтаксиса . Например, следующий алгебраический тип данных описывает простой язык, представляющий числовые выражения:

data Expression = Number Int
                | Add Expression Expression
                | Minus Expression Expression
                | Mult Expression Expression
                | Divide Expression Expression

Элемент такого типа данных будет иметь такую ​​форму, как Mult (Add (Number 4) (Minus (Number 0) (Number 1))) (Number 2).

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

Объяснение

Что происходит, так это то, что существует тип данных, который может быть одним из нескольких типов . Каждый тип вещей связан с идентификатором, называемым конструктором , который можно рассматривать как своего рода тег для такого рода данных. Каждый конструктор может нести разные типы данных. Конструктор может не содержать данных (например, «Пустой» в приведенном выше примере) или один фрагмент данных (например, «Лист» имеет одно значение типа Int) или несколько фрагментов данных (например, «Узел» имеет два значения Дерева. ).

Чтобы что-то сделать со значением этого алгебраического типа данных Tree, он деконструируется с использованием процесса, называемого сопоставлением с образцом . Он включает сопоставление данных с рядом шаблонов . В приведенном выше примере функции «depth» свой аргумент сопоставляется с тремя образцами. Когда функция вызывается, она находит первый шаблон, соответствующий ее аргументу, выполняет любые привязки переменных, которые встречаются в шаблоне, и оценивает выражение, соответствующее шаблону.

Каждый шаблон выше имеет форму, которая напоминает структуру некоторого возможного значения этого типа данных. Первый шаблон просто соответствует значениям конструктора Empty . Второй шаблон соответствует значениям конструктора Leaf . Шаблоны рекурсивны, поэтому данные, связанные с этим конструктором, сопоставляются с шаблоном «n». В этом случае идентификатор в нижнем регистре представляет шаблон, который соответствует любому значению, которое затем привязывается к переменной с этим именем - в этом случае переменная « n» привязана к целочисленному значению, хранящемуся в типе данных, для использования в выражение для оценки.

Рекурсия в шаблонах в этом примере тривиальна, но возможный более сложный рекурсивный шаблон будет примерно таким . Рекурсивные паттерны в несколько слоев используются, например, при балансировке красно-черных деревьев , что включает случаи, когда требуется рассматривать цвета в несколько слоев. Node (Node (Leaf 4) x) (Node y (Node Empty z))

Приведенный выше пример функционально эквивалентен следующему псевдокоду:

 switch on (data.constructor)
   case Empty:
     return 0
   case Leaf:
     let l = data.field1
     return 1
   case Node:
     let l = data.field1
     let r = data.field2
     return 1 + max (depth l) (depth r)

Сравнение этого с сопоставлением с образцом укажет на некоторые преимущества алгебраических типов данных и сопоставления с образцом. Первое преимущество - безопасность типов . Псевдокод выше полагается на старание программиста, чтобы не получить доступполе2когда конструктор, например, является Leaf. Также типполе1 отличается для Leaf и Node (для Leaf это Int; для узла этоДерево), поэтому система типов столкнется с трудностями при назначении ей статического типа безопасным способом в традиционной структуре данных записи . Однако при сопоставлении с образцом тип каждого извлеченного значения проверяется на основе типов, объявленных соответствующим конструктором, и сколько значений может быть извлечено, известно на основе конструктора, поэтому он не сталкивается с этими проблемами.

Во-вторых, при сопоставлении с образцом компилятор статически проверяет, все ли случаи обработаны. Если один из описанных выше случаев функции глубины отсутствует, компилятор выдаст предупреждение, указывающее на то, что случай не обрабатывается. Эта задача может показаться простой для простых шаблонов, описанных выше, но со многими сложными рекурсивными шаблонами задача становится сложной для обработки для обычного человека (или компилятора, если он должен проверять произвольные вложенные конструкции if-else). Точно так же могут быть шаблоны, которые никогда не совпадают (т. Е. Уже охвачены предыдущими шаблонами), и компилятор также может проверять и выдавать предупреждения для них, поскольку они могут указывать на ошибку в рассуждении.

Не путайте эти шаблоны с шаблонами регулярных выражений , используемыми при сопоставлении строковых шаблонов. Цель аналогична: проверить, соответствует ли часть данных определенным ограничениям, и если да, извлечь соответствующие части для обработки. Однако механизм совсем другой. Этот вид сопоставления с образцом для алгебраических типов данных соответствует структурным свойствам объекта, а не символьной последовательности строк.

Теория

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

Например, тип данных Haskell:

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

в теории типов представлен как с конструкторами, так и с . ${\ Displaystyle \ лямбда \ альфа. \ му \ бета .1+ \ альфа \ раз \ бета}$${\ displaystyle \ mathrm {nil} _ {\ alpha} = \ mathrm {roll} \ (\ mathrm {inl} \ \ langle \ rangle)}$${\ displaystyle \ mathrm {cons} _ {\ alpha} \ x \ l = \ mathrm {roll} \ (\ mathrm {inr} \ \ langle x, l \ rangle)}$

Тип данные Haskell Список также могут быть представлены в теории типа в несколько иной форме, таким образом: . (Обратите внимание , как и конструкции обратные по отношению к оригиналу.) Оригинальное образование указана функция типа, корпус которого был рекурсивный типом. В новой версии указана рекурсивная функция для типов. (Переменная типа используется, чтобы предложить функцию, а не базовый тип, например , так как она похожа на греческую f .) Функция также должна теперь применяться к ее типу аргумента в теле типа. ${\ Displaystyle \ му \ фи. \ лямбда \ альфа .1+ \ альфа \ раз \ фи \ \ альфа}$${\ displaystyle \ mu}$${\ displaystyle \ lambda}$${\ displaystyle \ phi}$${\ displaystyle \ beta}$${\ displaystyle \ phi}$${\ displaystyle \ phi}$${\ displaystyle \ alpha}$

Для целей примера со списком эти две формулировки существенно не отличаются; но вторая форма позволяет выражать так называемые вложенные типы данных , т. е. те, в которых рекурсивный тип параметрически отличается от исходного. (Дополнительные сведения о вложенных типах данных см. В работах Ричарда Берда , Ламберта Меертенса и Росса Патерсона.)

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

Языки программирования с алгебраическими типами данных

Многие языки программирования включают алгебраические типы данных в качестве первоклассного понятия, в том числе:

Смотрите также

• Несвязный союз
• Обобщенный алгебраический тип данных
• Начальная алгебра
• Тип частного
• Tagged union
• Теория типов
• Шаблон посетителя

использованная литература