На какие традиционные структуры данных сумм и продуктов он ссылается?
В теории типов регулярные структуры данных могут быть описаны в терминах сумм, продуктов и рекурсивных типов.,Это приводит к алгебре для описания структур данных (и так называемым алгебраическим типам данных ).Такие типы данных распространены в статически типизированных функциональных языках, таких как ML или Haskell.
Продукты
Продукты можно рассматривать как теоретико-типовое представление "структур""или" кортежи ".
Формально, PFPL, Ch 14:
Двоичный продукт двух типов состоит из упорядоченных пар значений, по одному от каждоговведите в указанном порядке.Соответствующие формы исключения являются проекциями, которые выбирают первый и второй компонент пары.Тип нулевого продукта или единицы состоит исключительно из уникального «нулевого кортежа» без значений и не имеет связанной исключающей формы.
Суммы
Типы сумм выражают выбор между вариантами структуры данных.Иногда их называют «объединение типов» (как в C).Многие языки не имеют представления о типах сумм.
PFPL, ch 15:
Большинство структур данных включают альтернативы, такие как различие между листом и внутренним узлом в дереве, иливыбор во внешней форме части абстрактного синтаксиса.Важно отметить, что выбор определяет структуру стоимости.Например, у узлов есть дети, а у листьев нет, и так далее.Эти понятия выражаются типами сумм, в частности двоичной суммой, которая предлагает выбор из двух вещей, и нулевой суммой, которая предлагает выбор без вещей.
Рекурсивные типы
Наряду с продуктами и суммами мы можем ввести рекурсию, поэтому тип может быть определен (частично) в терминах самого себя.Хорошие примеры включают деревья и списки.
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 (Ссылка кажется мертвой)
- Виды, функторы и типы, О, Боже, Брент Йорги, http://www.cis.upenn.edu/~byorgey/papers/species-pearl.pdf - очень хороший обзор алгебры, Хаскеллтипы данных и связь с комбинаторными видами из математики.