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

Ответ 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, являющемуся "продуктом набора конструкторов", однако прошло несколько лет с тех пор, как я убежал из университета, поэтому я больше не могу вспомнить специфику.

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

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

Ответ 3

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

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

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

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

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

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

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

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

Ответ 4

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

data Bool = False | True

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

data Pair a b = Pair a b

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

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

Ответ 5

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

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

Ответ 6

@Timbo:

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

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

Ответ 7

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

Ответ 8

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

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

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

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

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