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

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

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

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

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

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

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

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

Примеры [ править ]

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

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

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]в ML.

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

 дерево  данных =  пусто  |  Leaf  Int  |  Узловое  дерево  Дерево

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

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

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

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

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

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

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

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

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

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

Объяснение [ править ]

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

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

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

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

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

 переключить  на  ( данные . конструктор )  регистра  Пустой :  возврат  0  случай  лист :  пусть  л  =  данные . field1  возвращает  1  регистр  Узел :  let  l  =  data . field1  пусть  r  =  data . field2  return  1  +  max  ( глубина  l )  ( глубина  r )

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

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

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

Теория [ править ]

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

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

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

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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

Эта статья основана на материалах, взятых из алгебраического типа данных в Free On-line Dictionary of Computing до 1 ноября 2008 г. и включенных в соответствии с условиями «перелицензирования» GFDL версии 1.3 или новее.