От моноидов к алгебрам де Моргана. Строим абстракции на Haskell

в 18:40, , рубрики: haskell, абстракция, алгебра везде, математика, моноид, функциональное программирование

Что общего у нормального распределения, конечных автоматов, хеш-таблиц, произвольных предикатов, строк, выпуклых оболочек, афинных преобразований, файлов конфигураций и стилей 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 можно почитать в статьях:

Алгебры де Моргана

Для многих объектов существует несколько способов композиции и одним моноидом тут не обойтись. Если таких способов два, то говорят о кольцах, полукольцах, решётках и различных алгебрах. Рассмотрим несколько примеров, наводящих на мысль об общности алгебраической структуры, лежащей в их основе.

Булева алгебра

Что мы знаем о булевой алгебре:

  • Определена на множестве значений {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

Источник

Поделиться

* - обязательные к заполнению поля