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

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

дерево данных = Empty | Leaf Int | Дерево узлов

Здесь Пустопредставляет пустое дерево, Листсодержит фрагмент данных, а Узелорганизует данные в ветви.

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

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

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

depth :: Tree ->Int depth Empty = 0 depth (Leaf n) = 1 depth (Node lr) = 1 + max (глубина l) (глубина r)

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

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

data Expression = Number Int | Добавить выражение Expression | Минус Выражение Выражение | Mult Expression Expression | Выражение разделения Выражение

Элемент такого типа данных будет иметь такую ​​форму, как Mult (Добавить (Число 4) (Минус (Число 0) (Число 1))) (Число 2).

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

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

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

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

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

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

включить (data.constructor) case Empty: вернуть 0 case Leaf: let l = data.field1 вернуть 1 case Node: let l = data.field1 let r = data.field2 return 1 + max (depth l) (depth r)

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

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

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

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

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

список данных a = Nil | Минусы a (Список a)

представлен в теории типов как $\lambda \; \alpha .\; \mu \; \beta .1\; +\; \alpha \; \times \; \beta \; \{\backslash \; displaystyle\; \backslash \; lambda\; \backslash \; alpha.\; \backslash \; mu\; \backslash \; beta.1+\; \backslash \; alpha\; \backslash \; times\; \backslash \; beta\}$с конструкторами $nil\; \alpha \; =\; roll\; (inl\; ⟨⟩)\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{nil\}\; \_\; \{\backslash \; alpha\}\; =\; \backslash \; mathrm\; \{roll\}\; \backslash \; (\backslash \; mathrm\; \{inl\}\; \backslash \; \backslash \; langle\; \backslash \; rangle)\}$и $cons\; \alpha \; xl\; =\; roll\; (inr\; ⟨Икс,\; l⟩)\; \{\backslash \; Displaystyle\; \backslash \; mathrm\; \{cons\}\; \_\; \{\backslash \; alpha\}\; \backslash \; x\; \backslash \; l\; =\; \backslash \; mathrm\; \{roll\}\; \backslash \; (\backslash \; mathrm\; \{inr\}\; \backslash \; \backslash \; langle\; x,\; l\; \backslash \; rangle)\}$.

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

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

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

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

• Цейлон
• Чистый
• Coq
• C ++
• Elm
• Flow
• F#
• F*
• Haskell
• Haxe
• Hope
• Idris
• Java 15 (предварительная версия)
• Julialang
• Kotlin
• Limbo
• Language Of Temporal Ordering Спецификация (LOTOS)
• Mercury
• Miranda
• Nemerle
• Nim
• OCaml
• Opa
• OpenCog
• Perl
• PureScript
• Racket
• Причина
• Rust
• Scala
• Standard ML
• Swift
• Tom
• TypeScript
• Visual Prolog

• Disjoint union
• Generalized algebraic data type
• Исходная алгебра
• Тип фактора
• Объединение с тегами
• Теория типов
• Шаблон посетителей

Эта статья основана на материале, взятом из алгебраического типа данных в Бесплатный он-лайн словарь по вычислительной технике до 1 ноября 2008 г. и включен в соответствии с условиями «перелицензирования» GFDL, версия 1.3 или l атер.