Что означает алгебраический в алгебраических типах данных в функциональных языках?

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

Читая первые несколько разделов статьи в Википедии по этому вопросу, я вижу, что связанные списки являются одним из примеров такого ADT. Другой приведенный пример - деревья, и, честно говоря, я не вижу в них гораздо большего количества алгебры, чем я вижу в «ванильной» иерархии классов, таких как игрушечные примеры, такие как знакомый класс Animal с, скажем, подклассом Cat. и еще один - Собака. Я могу, например, сопоставить все эти типы с образцом, скажем, с помощью Scala.

Итак, в чем же секретный соус, которого мне здесь явно не хватает?


functional-programming pattern-matching algebraic-data-types
person funcprogrammingnewbie    schedule 31.07.2014    source источник
comment
ADT означает абстрактный тип данных, а не алгебраический тип данных.   -  person Barmar    schedule 31.07.2014
comment
Хм, похоже, что я могу ошибаться. В ФП ADT действительно означает алгебраический.   -  person Barmar    schedule 31.07.2014
comment
Этот вопрос кажется не по теме, потому что он больше подходит для cs.stackexchange.com.   -  person Barmar    schedule 31.07.2014
comment
@Barmar, я определенно хотел бы увидеть нетехнические нетехнические объяснения этого вопроса. Я считаю, что это элементарно для людей, которые программируют на функциональных языках.   -  person funcprogrammingnewbie    schedule 31.07.2014
comment
В основном, я думаю, это означает, что новые типы создаются из более простых типов с использованием алгебры, аналогичной теории множеств.   -  person Barmar    schedule 31.07.2014
comment
Например. NewType = OldType1 | OldType2, что соответствует установленному оператору UNION.   -  person Barmar    schedule 31.07.2014
comment
Итак, любой составной тип был бы алгебраическим?   -  person funcprogrammingnewbie    schedule 31.07.2014
comment
составной тип обычно относится к типам, группирующим элементы, например структуры и массивы. Алгебраические типы допускают другие типы композиции, такие как оператор ИЛИ в моем предыдущем примере.   -  person Barmar    schedule 31.07.2014
comment
Например. связанный список является либо NULL (представляет пустой список) ИЛИ составным типом, содержащим элемент (head) и другой связанный список (rest списка)   -  person Barmar    schedule 31.07.2014
comment
И может быть выражено, скажем, через наследование, как в моем примере с классом Animal Animal?   -  person funcprogrammingnewbie    schedule 31.07.2014
comment
Здесь пора спать. Я вернусь после того, как проснусь.   -  person funcprogrammingnewbie    schedule 31.07.2014
comment
Нет, это отличается от наследования. В ООП вы начинаете с базового класса, а затем уточняете и расширяете его подклассами. В ADT вы начинаете с примитивных типов и объединяете их в более сложные типы.   -  person Barmar    schedule 31.07.2014
comment
Напишите, пожалуйста, ответ, и я смогу его выбрать, как только разберусь в нюансах.   -  person funcprogrammingnewbie    schedule 31.07.2014
comment
Я бы предпочел, чтобы кто-то с реальным опытом в FP написал более точный ответ.   -  person Barmar    schedule 31.07.2014
comment
Короче говоря, это потому, что вы можете определить алгебру над типами вместо простых чисел - следовательно, термины «тип суммы» и «тип продукта» на самом деле являются сложением и умножением типов (а функции - возведением в степень). Посмотрите вторую половину первого ответа здесь и это сообщение в блоге.   -  person molbdnilo    schedule 31.07.2014
comment
возможный дубликат Отсутствует определение "алгебраического типа данных" в книге Learn You a Haskell for Great Good   -  person Aadit M Shah    schedule 26.08.2015
comment
возможный дубликат Почему в имени алгебраического типа данных используется алгебраический? < / а>   -  person Mirzhan Irkegulov    schedule 27.08.2015
comment
прочтите все в stackoverflow.com/q/9190352/2007884 вместе с возможными дополнительными ссылками в описании, включая сам вопрос. Это должно ответить на ваш вопрос.   -  person kram1032    schedule 18.09.2015

Ответы (1)


arrow_upward
0
arrow_downward

Я ответил на этот вопрос до [1]. Тем не менее, я кратко повторю, почему в этом ответе мы описываем типы данных как «алгебраические».

Для начала давайте разберемся, что означает слово «алгебра». Слово «алгебра» происходит от арабской фразы «аль-джабр», что означает «воссоединение сломанных частей» [2]. Тема разбиения проблем на более простые (декомпозиция) с последующим объединением решений этих проблем в окончательное решение (перекомпоновка) является центральной для нескольких областей, включая программирование [3].

Фраза «аль-джабр» была частью названия известной статьи по уравнениям [4 ] написан персидским математиком Мухаммадом аль-Хорезми, более известным на латыни как Алгоритми. Слово «алгоритм» произошло от его имени. Название статьи было «Китаб аль-Джабр вал-Мукабала», что переводится как «Правила реинтеграции и сокращения». Именно эта газета познакомила Запад с арабскими цифрами.

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

Операция декартового произведения производит типы продуктов [5]. Например, если у нас есть два типа данных, Int и Char, то декартово произведение Int × Char - это набор всех возможных пар целых чисел и символов. Значение типа Int × Char - это пара (0, 'a').

Операция непересекающегося объединения производит типы суммы [6]. Например, если у нас есть два типа данных, Int и Char, то непересекающееся объединение Int + Char - это набор всех целых чисел с тегами Int или символов с тегами Char. Значения типа Int + Char - это пары (0, Int) и ('a', Char).

Алгебраические типы данных позволяют определять типы данных алгебраически. Например, следующий тип данных Shape представляет собой непересекающееся объединение типов Circle и Rectangle, которые являются декартовыми произведениями типа Double:

data Shape = Circle    { x  :: Double, y  :: Double, r  :: Double }
           | Rectangle { x1 :: Double, y1 :: Double, x2 :: Double, y2 :: Double }

По этой причине они называются «алгебраическими» типами данных.

person Aadit M Shah    schedule 26.08.2015