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

Question

Я пытаюсь полностью понять все концепции Хаскелла.

Чем алгебраические типы данных похожи на общие типы, например, в C# и Java? И чем они отличаются? Что в них такого алгебраического?

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

Answer 1

"Алгебраические типы данных" в Haskell поддерживают полный параметрический полиморфизм, который является более технически правильным именем для обобщенных типов, в качестве простого примера тип данных списка:

 data List a = Cons a (List a) | Nil

Это эквивалентно (насколько это возможно, игнорируя нестрогую оценку и т. Д.)

 class List<a> {
     class Cons : List<a> {
         a head;
         List<a> tail;
     }
     class Nil : List<a> {}
 }

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

[Редактировать: Спасибо Крису Конвею за указание на мою глупую ошибку, ADT, конечно, являются типами сумм, конструкторами, предоставляющими продукт / кортеж полей]

Answer 2

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

• + представляет типы сумм (непересекающиеся объединения, например, 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²

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

• Расширение: развертывание точки исправления может быть полезно для размышлений о списках. 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′

---

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

• Виды, функторы и типы, Oh My!, Brent A. Yorgey, Haskell'10, 30 сентября 2010 г., Балтимор, Мэриленд, США
• Клоуны слева от меня, шутники справа (Разбор структур данных), Conor McBride POPL 2008

Answer 3

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

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

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

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

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

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

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

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

Answer 4

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

data Bool = False | True

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

data Pair a b = Pair a b

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

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

Answer 5

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

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

Answer 6

@Timbo:

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

ADT (типы сумм) также в некотором роде похожи на тегированные объединения или варианты типов в C или C++.

Answer 7

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

Answer 8

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

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

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

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

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