Алгебраические типы данных и их использование в программировании

[lionet]

Алгебраические типы данных и их использование в программировании

Роман Душкин

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

Comments

[thedeemon]

Извиняюсь, если вопрос прозвучит сумбурно.

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

У нас есть базовые элементы-типы и две операции - умножение и сложение, которые дают нам строить более сложные типы. Да, слагаемым может быть произведение, но может и не быть. Зачем говорить, что любая сумма - именно сумма произведений?

[thedeemon]

Я тоже так подумал, но это уже следствие, а не определение.
Для определения АТД достаточно, что это сумма слагаемых, где слагаемые - типы. Уточнять, что это произведения, в которых число множителей может быть 1 или 0 несколько излишне, имхо.

Мы же не говорим, что в декартовом произведении типов множители - это суммы, где число слагаемых может быть 1. :)

[thedeemon]

"Для произведения приходится пользоваться произведением". Логично. :)

[antilamer]

> Декартово произведение - лишь частный случай
Нет.
Каждый конструктор алгебраического типа имеет вид Consi t1 t2 ... - т.е. декартово произведение типов t1, t2,... , а то, что это за типы - никакого значения не имеет.

[thedeemon]

Это смотря в каком языке. Например, в окамле там один тип - т.е. либо Cons, либо Cons of t, где t может быть в том числе произведением (например Cons of int * char * 'a list).

Но в паттерн матчинге мы такую штуку запишем как Cons x и если x - произведение, то оно будет в скобках как тупл, и все это вместе можно заменить одним _. Если бы в определении типа был набор t1 t2 и т.д, пришлось бы писать много _, когда значение не важно.

Короче, имхо, в статье частный случай хаскелла обобщили до определения, что некрасиво.

[antilamer]

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

Fork a (Tree a) (Tree a) <-> Fork (a, Tree a, Tree a)

Cons of t - это декартово произведение единственного типа t.

В общем, тут нет обобщения, тут одно из нескольких эквивалентных определений.

[thedeemon]

Но одно из определений избыточно. :)

Когда рассказываем про А -> B, мы же не вводим в определение тот факт, что А - это декартово произведение, в котором может быть один множитель или ни одного - (). Зачем тогда делать такое в определении суммы? Просто из-за синтаксиса Хаскелла?

[antilamer]

Согласен :)

[thedeemon]

Кстати, запись "Cons t1 t2 t3" выглядит совершенно логично, если это не произведение, а описание функции Cons с параметрами t1 t2 t3. Но если это так, то надо переписывать всю статью. :)

[thedeemon]

Выше по ветке видно, что речь не про произвольную функцию, а про конструктор АТД. Т.е. в записи "data OneOrTwo = One Int | Two Int Int" не является ли случайно Two функцией двух аргументов, возвращающей OneOrTwo.

[nponeccop]

Тут мы залезаем в очень неприятную область - а именно, подходим к вопросу "что такое функции в Хаскеле". Советую на этом завершить дискуссию, т.к. в этой области мы все профаны. При построении семантики Хаскеля с помощью GRS между функциями и конструкторами есть отличия.