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

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

• + представляет типы сумм (непересекающиеся объединения, например Either).
• • представляет типы продуктов (например, структуры или кортежи)
• X для одноэлементного типа (например,data X a = X a)
• 1 для типа устройства ()
• и μ для наименее фиксированной точки (например, рекурсивные типы), обычно неявные.

С некоторыми дополнительными обозначениями:

• X² на X•X

фактически, вы можете сказать (после Брента Йорги), что тип данных Haskell является регулярным, если он может быть выражен в условия 1,X,+,•, и наименее фиксированная точка.

С помощью этой нотации, мы можем кратко описать многие постоянные структуры данных:

• единицы измерения:data () = ()

  1

• варианты: data Maybe a = Nothing | Just a

  1 + X

• список: data [a] = [] | a : [a]

  L = 1+X•L

• бинарные деревья: data BTree a = Empty | Node a (BTree a) (BTree a)

  B = 1 + X•B²

другие операции hold (взяты из статьи Брента Йорги, перечисленные в ссылках):

• расширение: развертывание точки исправления может быть полезно для размышления о списках. L = 1 + X + X² + X³ + ... (то есть списки либо пусты, либо имеют один элемент, либо два элемента, либо три, либо ...)

• состав ◦, С учетом типа F и G состав F ◦ G - это тип, который строит "F-структуры, сделанные из G-структур" (например,R = X • (L ◦ R) ,где L это списки, это розовое дерево.

• дифференцирование, производная от типа данных D (заданного как D')-это тип D-структур с одним "отверстием", то есть выделенным местоположением, не содержащим никаких данных. Что удивительно удовлетворяет тем же правилам, что и для дифференциации в исчисление:

  1′ = 0

  X′ = 1

  (F + G)′ = F' + G′

  (F • G)′ = F • G′ + F′ • G

  (F ◦ G)′ = (F′ ◦ G) • G′

---

ссылки:

• виды и функторы и типы Ой! А. Йорги Брент, Хаскелл’10, 30 сентября 2010 года, Балтимор, штат Мэриленд, США
• клоуны слева от меня, джокеры справа (рассечение данных Структуры), Конор Макбрайд ПОПЛ 2008

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

например, предположим, что у вас есть тип "элементы списка" и a тип списка." В качестве операций у вас есть "пустой список", который является 0-аргументом функция, возвращающая "список", и функция "минусы", которая принимает два аргумента, "элемент списка" и "список", а также создать "список."

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

• в наборе "список" могут быть элементы, которые не могут быть построены из "пустого списка" и "минусов операции", так называемый "мусор". Это могут быть списки, начиная с какого-то элемента, который упал с неба, или циклы без начала, или бесконечные списки.

• результаты "минусов" применяются к разным аргументы могут быть равными, например, сохранение элемента в непустом списке может быть равно пустому списку. Это иногда называют "путаницей".

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

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

Это становится более сложным для полиморфных типов ...

простая причина, по которой они называются алгебраическими; есть как сумма (логическая дизъюнкция), так и произведение (логическая конъюнкция) типов. Тип суммы является дискриминированным объединением, например:

data Bool = False | True

тип продукта-это тип с несколькими параметрами:

data Pair a b = Pair a b

В O'CAML "продукт" сделан более явным:

type 'a 'b pair = Pair of 'a * 'b

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

@olliej: ADTs на самом деле являются типами "sum". Кортежи-это продукты.

@Timbo:

вы в основном правы в том, что это похоже на абстрактный класс дерева с тремя производными классами (пустой, лист и узел), но вам также нужно будет обеспечить гарантию того, что кто-то, использующий ваш класс дерева, никогда не сможет добавить новые производные классы, поскольку стратегия использования типа дерева данных заключается в написании кода, который переключается во время выполнения на основе типа каждого элемента в дереве (и добавление новых производных типов нарушит существующий код). Вы можете сортировать представьте, что это становится неприятным в C# или C++, но в Haskell, ML и OCaml это занимает центральное место в дизайне языка и синтаксисе, поэтому стиль кодирования поддерживает его гораздо более удобным способом, с помощью сопоставления шаблонов.

ADT (sum types) также похожи на союзы тегами или типы вариант в C или C++.

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

для меня концепция алгебраических типов данных Хаскелла всегда выглядела как полиморфизм в OO-языках, таких как C#.

посмотрите на пример из http://en.wikipedia.org/wiki/Algebraic_data_types:

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

Это может быть реализовано в C# как базовый класс TreeNode, с производным классом Leaf и производным классом TreeNodeWithChildren, и если вы хотите даже производный класс EmptyNode.

(хорошо, я знаю, никто никогда этого не сделает, но на по крайней мере, ты можешь это сделать.)