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

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

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

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

Don Stewart 6.05.2011 20:34:41
8 ОТВЕТОВ
РЕШЕНИЕ

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

22
16.10.2011 21:41:15
Дженерики используются так по-разному, что единственное реальное общее основание - это «тип полиморфизма, которого у моего языка нет (или нет), но который мы планируем добавить (или добавить).
wnoise 26.09.2008 21:07:50
Этот ответ не объясняет, в каком смысле типы данных Haskell являются алгебраическими .
Don Stewart 6.05.2011 21:24:53
На самом деле, я думаю, что аналогия не совсем корректна - data List aэто конструктор типов, но Cons и Nil являются конструкторами данных - они обозначают значения типа List a (различие важно, потому что они находятся в отдельных пространствах имен, так что вы можете и часто имеют конструкторы типов и данных с одним и тем же именем).
Martin 29.08.2012 10:31:52

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

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

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

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

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

0
19.08.2008 19:58:06

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

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

9
19.08.2008 20:53:36
ADT не являются (просто) типами суммы.
Richard Simões 25.07.2014 17:38:19
Абстрактные типы данных являются типами продуктов. Они структурно изоморфны кортежам, за исключением того, что их члены помечены.
Mark Cidade 30.05.2016 14:34:48

@Timbo:

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

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

3
30.08.2008 07:21:17
Меня смущает «поскольку стратегия использования типа данных Tree заключается в ...» как причина, по которой тип суммы не может быть смоделирован как наследственное (под) дерево. Ваши операции распределены по различным классам (переключение на основе типов является подмножеством сопоставления с образцом), поэтому новые узлы будут иметь любое поведение по умолчанию, которое вы определили в своем классе TreeNode (или который определяет ваш язык) - возможно, ошибка, указывающая, что абстрактный TreeNode и вам нужно реализовать соответствующий метод.
Frank Shearar 27.07.2011 20:42:55
Конечно, вы можете добавить к нему операции, требуемые для каждого типа узла, в качестве (виртуальной) функции-члена. Вот что такое ООП, по сути ...
vonbrand 8.01.2016 22:26:50

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

2
19.12.2008 22:49:23

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

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

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

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

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

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

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

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

20
13.03.2009 21:23:55

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

data Bool = False | True

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

data Pair a b = Pair a b

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

type 'a 'b pair = Pair of 'a * 'b
12
16.03.2009 01:28:07

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

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

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

  • за X•X

На самом деле, можно сказать (после Brent Йорги) , что тип данных 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′


Ссылки:

101
6.05.2011 21:29:25
Я нашел в главе 3 книгу «Реальный мир Haskell» (вы в соавторстве), где очень хорошо объясняются алгебраические типы данных. Особенно, если вы действительно новичок в Haskell и у вас нет опыта работы с компом.
rzetterberg 4.11.2011 13:35:14
haskell.org/haskellwiki/Abstract_data_type перечисляет двоичное параметризованное дерево в качестве примера для абстрактного типа данных, а haskell.org/haskellwiki/Algebraic_data_type утверждает, что абстрактный DT и алгебраический DT являются взаимоисключающими категориями. Или бинарное дерево здесь на самом деле не считается алгебраическим (несмотря на вопрос), так как вы на самом деле просто называете его «регулярным» !?
Raffael 9.01.2015 12:26:57