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

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

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

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

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

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

История

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

Примеры

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

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

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

или

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

Cons— это аббревиатура от cons truct. Многие языки имеют специальный синтаксис для списков, определенных таким образом. Например, Haskell и ML используют for или for соответственно и []квадратные Nilскобки :для целых списков. Обычно так пишется или на Haskell, или как или на ML.::ConsCons 1 (Cons 2 (Cons 3 Nil))1:2:3:[][1,2,3]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, тип данных является рекурсивным .

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

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

Таким образом, Treeданное to 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значения).

Чтобы что-то сделать со значением этого 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 также может быть представлен в теории типов в несколько иной форме, например: . (Обратите внимание, что конструкции и перевернуты по отношению к оригиналу.) Исходная структура задавала функцию типа, тело которой было рекурсивным типом. Пересмотренная версия определяет рекурсивную функцию для типов. (Переменная типа используется для обозначения функции, а не базового типа , такого как , поскольку она похожа на греческую f .) Теперь функцию также необходимо применить к типу ее аргумента в теле типа. $\mu \phi .\lambda \alpha .1+\alpha \times \phi \ \alpha$ $\mu$ $\lambda$ ${\ displaystyle \ фи }$ $\бета$ ${\ displaystyle \ фи }$ ${\ displaystyle \ фи }$ $\альфа$

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

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

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

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

Цейлон
Чистый
Кок ^[3]
С++ ^[4]
Вяз
Дарт ^[5]
Поток
Ф#
Ф*
Бесплатный Паскаль
Хаскелл ^[6]
Хаксе ^[7]
Надеяться
Идрис
Java (16 для типов продуктов, ^[8] 17 для типов сумм ^[9] )
Котлин ^[10]
Лимбо
Спецификация языка временного упорядочения (LOTOS)
Меркурий
Миранда
Немерль
Ним
OCaml
Опа
OpenCog
Перл
Чистый скрипт
Питон
Ракетка
Причина ^[11]
Ржавчина ^[12]
Скала
Стандартный ML
Быстрый
Том
Машинопись
Визуальный Пролог