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

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Алгебраический тип данных»  – Новости  · газеты  · книги  · ученый  · JSTOR (Октябрь 2015 г.) (Узнайте, как и когда удалить этот шаблон сообщения) Эта статья может быть слишком техническим для большинства читателей, чтобы понять. Пожалуйста помогите улучшить это к сделать понятным для неспециалистов, не снимая технических деталей. (Сентябрь 2017 г.) (Узнайте, как и когда удалить этот шаблон сообщения) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

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

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

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

Примеры

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

данные Список а = Ноль | Минусы а (Список а)

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

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

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

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

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

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

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

 глубина :: Дерево -> Int глубина Пустой = 0 глубина (Лист п) = 1 глубина (Узел л р) = 1 + Максимум (глубина л) (глубина р)

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

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

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

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

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

Объяснение

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

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

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

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

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

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

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

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

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

Теория

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

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

 данные Список а = Ноль | Минусы а (Список а)

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

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

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

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

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

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

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

Рекомендации

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