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

https://stackoverflow.com/questions/16770

08-06-2019
|

Вопрос

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

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

Я знаком с универсальной алгеброй, ее кольцами и полями, но имею лишь смутное представление о том, как работают типы 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, конечно же, представляют собой типы сумм, конструкторы, предоставляющие произведение/кортеж полей]

Другие советы

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

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

Использованная литература:

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

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

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

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

В наборе «Список» могут быть элементы, которые не могут быть построены из «пустого списка» и «операции минусов», так называемого «мусора».Это могут быть списки, начиная с какого -то элемента, который упал с неба, или петли без начала или бесконечных списков.
Результаты «минусов», применяемые к различным аргументам, могут быть равны, например,Признание элемента в непустые списка может быть равным пустому списку.Иногда это называют «путаницей».

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

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

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

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

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

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

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

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

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

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow