В компьютерном программировании , особенно в функциональном программировании и теории типов , алгебраический тип данных (АТД) является разновидностью составного типа , то есть типа, образованного путем объединения других типов.
Два общих класса алгебраических типов — это типы произведений (т. е. кортежи и записи ) и типы сумм (т. е. помеченные или непересекающиеся объединения , типы копроизведений или варианты типов ). [1]
Значения типа продукта обычно содержат несколько значений, называемых полями . Все значения этого типа имеют одинаковую комбинацию типов полей. Набор всех возможных значений типа продукта — это теоретико-множественное произведение, т. е. декартово произведение , наборов всех возможных значений его типов полей.
Значения типа суммы обычно группируются в несколько классов, называемых вариантами . Значение типа варианта обычно создается с помощью квазифункциональной сущности, называемой конструктором . Каждый вариант имеет свой собственный конструктор, который принимает указанное количество аргументов с указанными типами. Набор всех возможных значений типа суммы является теоретико-множественной суммой, т. е. непересекающимся объединением , множеств всех возможных значений его вариантов. Перечислимые типы являются особым случаем типов суммы, в которых конструкторы не принимают аргументов, поскольку для каждого конструктора определено ровно одно значение.
Значения алгебраических типов анализируются с помощью сопоставления с образцом , которое идентифицирует значение по его конструктору или именам полей и извлекает содержащиеся в нем данные.
Алгебраические типы данных были введены в Hope , небольшом функциональном языке программирования, разработанном в 1970-х годах в Эдинбургском университете . [2]
Одним из наиболее распространенных примеров алгебраического типа данных является односвязный список . Тип списка — это тип суммы с двумя вариантами: Nilдля пустого списка и для объединения нового элемента x со списком xs для создания нового списка. Вот пример того, как односвязный список будет объявлен в Haskell :Cons x xs
Список данных a = Ноль | Минусы a ( Список a ) или
данные [] а = [] | а : [ а ] Cons— это сокращение от cons turct. Во многих языках есть специальный синтаксис для списков, определенных таким образом. Например, в Haskell и ML используются []for Nil, :или ::for Cons, соответственно, и квадратные скобки для целых списков. Поэтому Cons 1 (Cons 2 (Cons 3 Nil))обычно записывается как 1:2:3:[]или [1,2,3]в Haskell, или как 1::2::3::[]или [1,2,3]в ML.
В качестве немного более сложного примера двоичные деревья можно реализовать на языке Haskell следующим образом:
данные Дерево = Пусто | Лист Целое | Узел Целое Дерево Дерево или
данные Двоичное дерево а = BTNil | BTNode а ( Двоичное дерево а ) ( Двоичное дерево а ) Здесь Emptyпредставляет собой пустое дерево, Leafпредставляет собой конечный узел и Nodeорганизует данные в ветви.
В большинстве языков, поддерживающих алгебраические типы данных, можно определять параметрические типы. Примеры приведены далее в этой статье.
Несколько похожий на функцию, конструктор данных применяется к аргументам соответствующего типа, выдавая экземпляр типа данных, к которому принадлежит конструктор типа. Например, конструктор данных Leafлогически является функцией Int -> Tree, что означает, что передача целого числа в качестве аргумента Leafсоздает значение типа Tree. Поскольку Nodeпринимает два аргумента самого типа Tree, тип данных является рекурсивным .
Операции над алгебраическими типами данных можно определить, используя сопоставление с образцом для извлечения аргументов. Например, рассмотрим функцию для нахождения глубины a Tree, приведенную здесь на Haskell:
глубина :: Дерево -> Целое глубина Пусто = 0 глубина ( Лист n ) = 1 глубина ( Узел n l r ) = 1 + макс ( глубина l ) ( глубина r ) Таким образом, Treeзаданный to depthможет быть построен с использованием любого из Empty, Leaf, или Nodeи должен быть сопоставлен для любого из них соответственно, чтобы иметь дело со всеми случаями. В случае Nodeшаблон извлекает поддеревья lи rдля дальнейшей обработки.
Алгебраические типы данных отлично подходят для реализации абстрактного синтаксиса . Например, следующий алгебраический тип данных описывает простой язык, представляющий числовые выражения:
данные Выражение = Число Int | Выражение Add Выражение | Выражение Minus Выражение | Выражение Mult Выражение | Выражение Divide Выражение Элемент такого типа данных будет иметь такую форму, как 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))
Рекурсивные шаблоны глубиной в несколько слоев используются, например, при балансировке красно-черных деревьев , где рассматриваются случаи, требующие рассмотрения цветов глубиной в несколько слоев.
Приведенный выше пример функционально эквивалентен следующему псевдокоду :
включить ( данные . конструктор ) случай Пусто : вернуть 0 случай Лист : пусть n = данные . поле1 вернуть 1 случай Узел : пусть l = данные . поле1 пусть r = данные . поле2 вернуть 1 + макс ( глубина l ) ( глубина r ) Преимущества алгебраических типов данных можно подчеркнуть, сравнив приведенный выше псевдокод с эквивалентом сопоставления с образцом.
Во-первых, есть типобезопасность . В приведенном выше примере псевдокода требуется усердие программиста, чтобы не получить доступполе2когда конструктор — это Leaf. Также типполе1отличается для Leafи Node. Для Leaf этоИнтно для Node этоДерево. Система типов столкнется с трудностями при назначении статического типа безопасным способом для традиционных структур данных записи . Однако при сопоставлении с образцом такие проблемы не возникают. Тип каждого извлеченного значения основан на типах, объявленных соответствующим конструктором. Количество значений, которые могут быть извлечены, известно на основе конструктора.
Во-вторых, при сопоставлении с образцом компилятор выполняет проверку на полноту, чтобы гарантировать обработку всех случаев. Если один из случаев функции глубины выше отсутствует, компилятор выдаст предупреждение. Проверка на полноту может показаться простой для простых образцов, но со многими сложными рекурсивными образцами задача вскоре становится сложной для среднего человека (или компилятора, если он должен проверять произвольные вложенные конструкции if-else). Аналогично могут быть образцы, которые никогда не совпадают (т. е. уже охвачены предыдущими образцами). Компилятор также может проверять и выдавать предупреждения для них, поскольку они могут указывать на ошибку в рассуждениях.
Не следует путать сопоставление шаблонов алгебраических типов данных с сопоставлением шаблонов строк регулярных выражений . Цель обоих вариантов схожа (извлечь части из фрагмента данных, соответствующих определенным ограничениям), однако реализация сильно отличается. Сопоставление шаблонов алгебраических типов данных сопоставляет структурные свойства объекта, а не последовательность символов строк.
Общий алгебраический тип данных — это возможно рекурсивный тип суммы типов продуктов . Каждый конструктор помечает тип продукта, чтобы отделить его от других, или, если есть только один конструктор, тип данных является типом продукта. Кроме того, типы параметров конструктора являются факторами типа продукта. Конструктор без параметров соответствует пустому продукту . Если тип данных рекурсивен, вся сумма продуктов оборачивается рекурсивным типом , и каждый конструктор также сворачивает тип данных в рекурсивный тип.
Например, тип данных Haskell:
Список данных a = Ноль | Минусы a ( Список a ) представлен в теории типов как конструкторы и .
Тип данных Haskell List также может быть представлен в теории типов в несколько иной форме, например: . (Обратите внимание, как конструкции и перевернуты относительно оригинала.) Исходная формация определяла функцию типа, тело которой было рекурсивным типом. Пересмотренная версия определяет рекурсивную функцию для типов. (Переменная типа используется для указания функции, а не базового типа , как , поскольку похожа на греческую f .) Функция теперь также должна применяться к ее типу аргумента в теле типа.
Для целей примера со списком эти две формулировки не имеют существенных различий; однако вторая форма позволяет выражать так называемые вложенные типы данных, т. е. те, в которых рекурсивный тип параметрически отличается от исходного. (Более подробную информацию о вложенных типах данных см. в работах Ричарда Берда , Ламберта Меертенса и Росса Патерсона.)
В теории множеств эквивалентом типа суммы является непересекающееся объединение , множество, элементами которого являются пары, состоящие из тега (эквивалент конструктора) и объекта типа, соответствующего тегу (эквивалент аргументов конструктора). [3]
Многие языки программирования включают алгебраические типы данных в качестве первоклассных понятий, в том числе:
В докладах приняли участие Род Берстолл, Дэйв Маккуин и Дон Саннелла о Hope, языке, который ввел алгебраические типы данных.
