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

Не путать с абстрактным типом данных .

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

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

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

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

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

История

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

Примеры

Односвязный список

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

 данных  Список   a   =   Nil   |   Минусы   а   (  перечислите   а  ) 

или

данные   []   а   =   []   |   а   :   [  а  ] 

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] в МЛ.

Двоичное дерево

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

 данных  Дерево   =   Пусто            |   Лист   Int            |   узлов   Int   Tree   Дерево 

или

данные   BinaryTree   a   =   BTNil                    |   BTNode   a   (  BinaryTree   a  )   (  BinaryTree   a  ) 

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

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

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

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

 глубина   ::   Дерево   ->   Int   глубина   Empty   =   0   глубина   (  Лист   n  )   =   1   глубина   (  Узел   n   l   r  )   =   1   +   max   (  глубина   l  )   (  глубина   r  ) 

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

Абстрактный синтаксис

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

 данных  Выражение   =   Число   Int                  |   Добавить   выражение   Выражение                  |   Минус   Выражение   Выражение                  |   Множественное   выражение   Выражение                  |   Разделить   выражение   Выражение 

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

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

Сопоставление с образцом

Основная статья: Сопоставление с образцом

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

Например, рассматривая двоичный файл Tree показанном выше примере, конструктор не может нести никаких данных (например, Empty) или один фрагмент данных (например, Leaf имеет одно значение Int) или несколько фрагментов данных (например, Node имеет два Tree ценности).

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

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

Рекурсия в шаблонах в этом примере тривиальна, но возможный более сложный рекурсивный шаблон будет выглядеть примерно так:

Node (Node (Leaf 4) x) (Node y (Node Empty z))

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

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

 включить  ​   (  data.constructor ​ ​  )     случай   Пустой  :       вернуть   0     случай   Лист  :       пусть   n   =   data  .  поле1       возвращает   1     случай   Узел  :       пусть   l   =   данные  .  поле1       пусть   r   =   данные  .  поле2       возвращает   1   +   макс   (  глубина   l  )   (  глубина   r  ) 

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

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

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

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

Теория

Основная статья: Рекурсивный тип данных

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

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

  данных  Список   a   =   Nil   |   Минусы   а   (  перечислите   а  ) 

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

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

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

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

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

Основная статья: Сравнение языков программирования (алгебраический тип данных)

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

• Цейлон
• Чистый
• Кок
• С++
• Вяз
• Дарт
• Поток
• Ф#
• Ф*
• Бесплатный Паскаль
• Хаскелл
• Смешанный
• Надеяться
• Идрис
• Java (16 для типов продуктов, 17 для типов сумм )
• Котлин
• Лимбо
• Спецификация языка временного упорядочения (LOTOS)
• Меркурий
• Миранда
• Немерль
• Nim
• OCaml
• Опа
• OpenCog
• Перл
• Чистый скрипт
• Питон
• Ракетка
• Причина
• Ржавчина
• Скала
• Стандартный ML
• Быстрый
• Том
• Машинопись
• Визуальный Пролог

См. также

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