Каковы структуры данных "суммы и продукты"?

Ответ 1

Каковы традиционные структуры данных сумм и продуктов, на которые он ссылается?

В теории типов регулярные структуры данных могут быть описаны в терминах сумм, продуктов и рекурсивных типов. Это приводит к алгебре для описания структур данных (и так называемых алгебраических типов данных). Такие типы данных распространены в статически типизированных функциональных языках, таких как ML или Haskell.

Продукция

Продукты можно рассматривать как теоретико-множественные представления "структур" или "кортежей".

Формально PFPL, Ch 14:

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

Сумма

Типы сумм выражают выбор между вариантами структуры данных. Иногда их называют "типами союзов" (как в С). Многие языки не имеют понятия типов сумм.

PFPL, ch 15:

Большинство структур данных связаны с альтернативами, такими как различие между лист и интерьер node в дереве, или выбор в самой внешней форме кусок абстрактного синтаксиса. Важно отметить, что выбор определяет структуру от стоимости. Например, узлы имеют дочерние элементы, но листьев нет, и поэтому вперед. Эти понятия выражаются типами сумм, в частности двоичными сумма, которая предлагает выбор из двух вещей, и нулевую сумму, которая предлагает выбор нет.

Рекурсивные типы

Наряду с продуктами и суммами мы можем ввести рекурсию, поэтому тип может быть определен (частично) в терминах самого себя. Хорошие примеры включают деревья и списки.

 data List a = Empty | a : List a

 data Tree a = Nil | Node a (Tree a) (Tree a)

Алгебра сумм, произведений и рекурсии

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

Отдельная переменная:

Int

Произведение двух типов (обозначающее пару):

Int * Bool

Сумма двух типов (обозначающая выбор между двумя типами):

Int + Bool

И некоторые константы:

1 + Int

где 1 - единичный тип, ().

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

<сильные > Примеры

Тип устройства, data () = ()

Кортеж, самый простой тип продукта: data (a,b) = (a,b)

Простой тип суммы, data Maybe a = Nothing | Just a

и его альтернативу,

и рекурсивный тип, тип связанных списков: data [a] = [] | a : [a]

При этом вы можете создавать довольно сложные структуры, комбинируя суммы, продукты и рекурсивные типы. Например. простые обозначения для списка произведений сумм произведений: [(Maybe ([Char], Double), Integer)] порождают некоторые довольно сложные деревья:

Ссылки

• Практические основы программирования Язык, Роберт Харпер, 2011, http://www.cs.cmu.edu/~rwh/plbook/book.pdf
• Быстрое введение в алгебру типов данных, http://blog.lab49.com/archives/3011 (Ссылка кажется мертвой)
• Виды и функторы и типы, Oh My!, Brent Yorgey, http://www.cis.upenn.edu/~byorgey/papers/species-pearl.pdf - имеет очень хороший обзор алгебры, Haskell типы данных и связь с комбинаторными видами из математики.

Ответ 2

Очень подробные ответы уже даны, но почему-то они не упоминают этот простой факт.

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

Это связано с теорией типов, определяющей тип как набор значений.

data MySumType = Foo Bool | Bar Char
data MyProductType = Baz (Bool, Char)

• Bool - это набор из 2 значений.
• Char - это набор из 256 значений.
• MySumType - это набор из 2 + 256 значений.
• MyProductType - это набор из 2 * 256 значений.

Теперь вы никогда не забудете, что есть.

Ответ 3

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

Примеры:

• Если a имеет тип a и b имеет тип b, то (a, b) имеет тип A x B, который является тип продукта.

• Тип списка со значениями формы Nil или Cons x xs представляет собой тип суммы .

Ensō, по-видимому, больше внимания уделяет графикам, чем эти древовидные алгебраические типы.

Ответ 4

Из лекций для курса Курсера "Языки программирования", предлагаемого Univ. Вашингтона:

"Почему продукт и сумма? Это связано с тем, что в булевой алгебре, где 0 является ложным, а 1 истинно, и работает как умножение и или работает как сложение".