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

«Алгебраические типы данных» в 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, конечно, являются типами сумм, конструкторами, предоставляющими продукт / кортеж полей]

алгебраические типы данных в 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 !, Брент А. Йорги, Haskell'10, 30 сентября 2010 г., Балтимор, Мэриленд, США.
• Слева от меня клоуны, справа от меня шутники (анализ структур данных), Conor McBride POPL 2008

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

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

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

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

• Результаты применения «против» к разным аргументам могут быть одинаковыми, например преобразование элемента в непустой список может быть равно пустому списку. Иногда это называют «замешательством».

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

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

С полиморфными типами все усложняется ...

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

data Bool = False | True

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

data Pair a b = Pair a b

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

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

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

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

@ Тимбо:

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

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

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

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

Взгляните на пример из http://en.wikipedia.org/wiki/Algebraic_data_types:

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

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

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