Что общего у нормального распределения, конечных автоматов, хеш-таблиц, произвольных предикатов, строк, выпуклых оболочек, афинных преобразований, файлов конфигураций и стилей CSS? А что объединяет целые числа, типы в Haskell, произвольные графы, альтернативные функторы, матрицы, регулярные выражения и статистические выборки? Наконец, можно ли как-то связать между собой булеву алгебру, электрические цепи, прямоугольные таблицы, теплоизоляцию труб или зданий и изображения на плоскости? На эти вопросы есть два важных ответа: 1) со всеми этими объектами работают программисты, 2) эти объекты имеют сходную алгебраическую структуру: первые являются моноидами, вторые — полукольцами, третьи — алгебрами де Моргана.
Если мы, программисты, научимся сами и научим компьютер работать с моноидами, полукольцами и прочими структурами, то всем нам работать станет легче. Потому что на алгебраические структуры накладываются определённые ограничения, а из ограничений следуют и определённые гарантии. Все эти ограничения и гарантии справедливы для всех представителей структуры, а это значит, что можно строить универсальный инструментарий для работы с моноидами, полукольцами, алгебрами и, следовательно, со всеми перечисленными выше и многими другими объектами. Посмотрите, сколько математиками определено алгебраических структур! И ведь для них есть теоремы, какие-то для программистов полезные, какие-то пока не очень, но все они надёжны, как самые лучшие библиотеки программ!
Всё становится ещё вкуснее, когда внутри структуры строятся гомоморфизмы — преобразования, сохраняющие структуру. Гомоморфизмы дают возможность "переключаться" с одного объекта структуры на другой — со списков на числа, с графов на матрицы, с регулярных выражений на графы, с электрических цепей на булевы выражения или на графическое изображения этих цепей! Ну а уж изоморфизмы — это вообще песня! Если программист считает что математика ему не нужна и что все эти морфизмы-шморфизмы это просто абстрактная чушь, то он лишает себя не только прекрасного, надёжного инструмента, но, самое главное, существенной части удовольствия от своей работы.
В этой статье мы покажем на примере алгебр де Моргана, как строить алгебраические абстракции, как определять для них гомоморфизмы и свободные алгебры, и как это можно использовать, конечно.
Статья рассчитана на тех, кто уже знает что такое классы типов, функторы, моноиды и, в целом, хорошо представляет себе что такое программирование на Haskell. С другой стороны, она может быть интересна всем, кто интересуется как в программировании строятся абстракции, и как их можно применить к реальным задачам.
Немного про моноиды
Моноиды — это абстракция композиции. В свою очередь, композиция — ключевое понятие в функциональном программировании. Именно поэтому моноиды встречаются здесь так часто и играют настолько важные роли. Про ценность и богатство применения моноидов говорилось и писалось много. Здесь мы перечислим основные их свойства, которые нам пригодятся в дальнейшем изложении.
Определение
Моноидом называется очень простая структура: это множество, на котором определена ассоциативная бинарная операция, имеющая единственный нейтральный элемент. Коммутативность операции не требуется, однако нейтральный элемент должен быть нейтральным, будучи как первым, так и вторым операндом.
В языке Haskell для моноидов определён класс Monoid:
class Monoid a where
mempty :: a
mappend :: a -> a -> aа библиотека Data.Monoid предоставляет ряд полезных экземпляров этого класса, таких как Sum, Product, First, Last, Endo и т.п.
Ключевыми свойствами моноида являются ассоциативность и единственность нейтрального элемента. Эти ограничения позволяют обобщать моноидальные операции для произвольного порядка выполнения (в том числе, и для параллельного).
Дуальный моноид
Для любого моноида можно определить дуальный ему моноид, в котором бинарная операция принимает аргументы в обратном порядке:
> Dual [1,2,3] <> Dual [5,6]
Dual { getDual = [5,6,1,2,3] }Связь со свёрткой
Хорошо известно, насколько полезным и универсальным инструментом является свёртка: с одной стороны, через свёртку выражается дюжина полезных универсальных функций, обрабатывающих коллекции, а с другой, сворачивать можно списки, деревья и прочие индуктивные коллекции. Свёрток определено достаточно много. Сворачивать коллекцию можно как справа, так и слева, это может повлиять и на результат (в зависимости от ассоциативности сворачивающей функции), и на эффективность вычислений. Сворачивать можно вводя начальный результат свёртки, на случай пустой коллекции, или обходясь без него, если есть гарантии, что коллекция не пуста. Поэтому в стандартной библиотеке Haskell и библиотеке Data.Foldable так много различных свёрток:
foldr, foldl, foldr1, foldl1, foldl', foldl1'Если же речь идёт о свёртке в моноид, достаточно одной функции, в силу ассоциативности моноидальной операции и гарантии наличия нейтрального элемента.
fold :: (Monoid m, Foldable t) => t m -> m Чаще используется вариант, позволяющий явно указывать какой именно моноид следует использовать для свёртки:
foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> mЕсли коллекция является функтором, то определение функции foldMap можно дать такое:
foldMap f = fold . fmap fСвободный моноид
Иногда существует возможность "переходить" между моноидами, напомним, такие преобразования называются гомоморфизмами. При этом существует такой моноид, из которого можно построить гомоморфизм в любой другой. Такой моноид называется свободным, его роль в Haskell играют списки.
Свободные структуры отражают свойства алгебраической системы, но ничего "не вычисляют", не изменяют данные и не теряют информации. В известном смысле, они представляют собой формальный язык для описания элемента алгебраической системы или категории, при этом гомоморфизмы можно рассматривать в качестве интерпретаторов этого языка. Такая аналогия нам пригодится в дальнейшем.
Подробнее о моноидах и их применении в Haskell можно почитать в статьях:
- Monoids Tour
- Monoids: Theme and Variations (Functional Pearl)
- Monoids and Finger Trees
- Finger Trees: A Simple General-purpose Data Structure
Алгебры де Моргана
Для многих объектов существует несколько способов композиции и одним моноидом тут не обойтись. Если таких способов два, то говорят о кольцах, полукольцах, решётках и различных алгебрах. Рассмотрим несколько примеров, наводящих на мысль об общности алгебраической структуры, лежащей в их основе.
Булева алгебра
Что мы знаем о булевой алгебре:
- Определена на множестве значений
{True, False}и описывается с помощью трёх операций: конъюнкции, дизъюнкции и отрицания. - Конъюнкция и дизъюнкция формируют моноиды.
- Элемент
Falseявляется нейтральным для дизъюнкции и поглощающим для конъюнкции. - Элемент
True, в свою очередь, нейтральный элемент для конъюнкции и поглощающий для дизъюнкции. - Отрицание является инволюцией, то есть, эта операция обратна самой себе.
- Выполняется закон де Моргана.
$$display$$neg (A wedge B) = neg A vee neg B,quad neg (A vee B) = neg A wedge neg B$$display$$
Автор: samsergey
