[#] [Перевод] Простые алгебраические типы данных
habrabot(difrex,1) — All
2015-12-27 13:00:03


_Это шестая статья из цикла «Теория категорий для программистов». Предыдущие статьи уже публиковались на Хабре:_ [0\. Теория категорий для программистов: предисловие][1] [1\. Категория: суть композиции][2] [2\. Типы и функции][3] [3\. Категории, большие и малые][4] [4\. Категории Клейсли][5] [5\. Произведения и копроизведения][6] В предыдущей статье были рассмотрены базовые операции над типами: произведение и копроизведение. Теперь покажем, что комбинирование этих механизмов позволяет построить многие из повседневных структур данных. Такое построение имеет существенное прикладное значение. Например, если мы умеем проверять на равенство базовые типы данных, а также знаем, как свести равенство произведения и копроизведения к равенстве компонент, то операторы равенства для составных типов можно вывести автоматически. В Haskell для обширного подмножества составных типов автоматически выводятся операторы равенства и сравнения, конвертация в строку и обратно и многие другие операции. Рассмотрим подробнее место произведения и копроизведения типов в программировании.

## Произведение типов

Каноническая реализация произведения типов в языках программирования — это пара. В Haskell пара является примитивным конструктором типов, а в C++ это относительно сложный шаблон из стандартной библиотеки. Строго говоря, произведение типов не коммутативно: нельзя подставить пару типа `(Int, Bool)` вместо `(Bool, Int)`, хотя они и содержат одни и те же данные. Однако произведение коммутативно с точностью до изоморфизма, задаваемого функцией `swap`, которая обратна самой себе:

swap :: (a, b) -> (b, a)
swap (x, y) = (y, x)

Можно рассматривать такие пары как различные форматы хранения одной и той же информации, как big endian и little endian. [Читать дальше →][7]

[1]: http://habrahabr.ru/post/245797/
[2]: http://habrahabr.ru/post/246009/
[3]: http://habrahabr.ru/post/247765/
[4]: http://habrahabr.ru/post/248257/
[5]: http://habrahabr.ru/post/249113/
[6]: http://habrahabr.ru/post/271927/
[7]: http://habrahabr.ru/post/274103/#habracut