Некоторое время назад в одном уютном камерном собрании я делал доклад о своей разработке — скриптовом лиспоподобном языке Liscript. Начал с азов — семантики вычисления списков, префиксной нотации… Дошел до произвольной арности стандартных операций:+ 1 2 3
=> 6
все интуитивно понятно, вопросов не возникает. Рассказываю про булевские значения, привожу пример:
< 1 2
=> true
тоже все понятно. И тут вопрос из зала: «а если 3 аргумента передать, как будет вычисляться?» Я решаю, что это хороший повод выпендриться умными терминами, и отвечаю: «точно так же — как свертка по моноиду» :) И тут же поправляясь — «хотя операция сравнения не является моноидом», пишу пример:
< 1 2 3
=> true
< 1 2 3 4 1 2
=> false
Все так же интуитивно понятно, вопросов не возникает и продолжаем дальше (благоразумно оставляя без рассмотрения вычисления примитивных операций на одном аргументе и вообще при отсутствии оных, а также вычитание/деление и прочие немоноидальные операции :)). Успешно миновав в докладе подобных камней, через некоторое время я подумал — а можно ли как-то изловчиться, и все-таки сделать операцию сравнения моноидом (в каком-либо смысле)? И мне кажется, мне это удалось. Заинтересовавшихся темой прошу под кат.
Вступление про моноиды для самых маленьких
Как всем хорошо известно, моноидом называется ассоциативная бинарная операция на заданном множестве, имеющая нейтральный элемент. Значит, для определения моноида нам надо задать 3 вещи:
- множество, на котором определена наша операция
- саму операцию, обладающую ассоциативностью
- нейтральный элемент (из вышеопределенного множества)
Освежим в памяти термины «нейтральный» и «ассоциативный». Обозначим нашу бинарную операцию mappend, нейтральный элемент mempty (чтобы потом было проще читать хаскельный кот и чтобы латекс на маркдаун не натягивать), тогда нейтральность элемента определяется как:
mappend mempty x = x
mappend x mempty = x
что можно можно перевести на пальцах как: если один из операндов нашей операции является нейтральным элементом, то результат операции является вторым операндом, другими словами — нейтральный элемент не изменяет результат. Ассоциативность же определяется как:
mappend x (mappend y z) = mappend (mappend x y) z
То есть при вычисления композиции из двух (и, как следствие, произвольного числа) операций результат не зависит от порядка вычислений, или, иными словами, неважно как расставлять скобки в длинном выражении (поэтому их можно вообще опустить).
Вообще говоря, моноид — это довольно общее понятие абстрактной алгебры и теории категорий (ведь широко известно, что даже те самые монады — это моноиды по определению), но в данной статье мы не будем глубоко погружаться в теоретические аспекты. Начнем с пары простых примеров: операция сложения на множестве целых (или натуральных/вещественных/комплексных) чисел. Ассоциативность присутствует, в качестве нейтрального элемента берем 0 из заданного множества. Операция умножения также является моноидом, с нейтральным элементом 1. Еще пример — операция конкатенации на множестве строк, с нейтральным элементом в виде пустой строки. Так же все законы моноида выполняются, хотя операция конкатенации не является коммутативной — но это и не требуется. Реализация моноидов сложения/умножения на языке Haskell тривиальна:
newtype Sum a = Sum a deriving (Eq, Ord, Show)
instance Num a => Monoid (Sum a) where
mempty = Sum 0
mappend (Sum x) (Sum y) = Sum $ x + y
newtype Product a = Product a deriving (Eq, Ord, Show)
instance Num a => Monoid (Product a) where
mempty = Product 1
mappend (Product x) (Product y) = Product $ x * y
Здесь мы фактически определили конкретные реализации mempty и mappend по описанным выше правилам. Класс типов Monoid автоматически предоставляет нам операцию свертки mconcat любого контейнера (списка, дерева — любого, на котором определена операция свертки) по любому моноиду: на примере списка — мы начинаем с нейтрального элемента mempty в качестве результата свертки и идем последовательно по списку, обновляя результат через нашу моноидальную бинарную операцию mappend с текущим элементом списка. На примере числового списка, свертка его по моноиду Sum даст нам сумму элементов списка, а Product — произведение. Точно таким же образом вычисляются конструкции:
+ 4 5 6 7
=> 22
* 2 3 4 5
=> 120
В лиспах (оставляя в стороне вопрос о вычислении без аргументов). Проверим хаскельные реализации:
*MyMonoid> mconcat $ map Sum []
Sum 0
*MyMonoid> mconcat $ map Sum [1..10]
Sum 55
*MyMonoid> mconcat $ map Product []
Product 1
*MyMonoid> mconcat $ map Product [1..10]
Product 3628800
Как видим, все работает.
Операция минимум
Теперь возьмем пример поинтереснее — бинарную операцию минимума на числовом множестве. Является ли она моноидом? Операция ассоциативна, множество задано. Единственная проблема — определение нейтрального элемента. Нам нужен такой элемент в нашем множестве, который был бы не меньше любого другого элемента. Если наше множество имеет точную верхнюю грань (например, тип uint8 имеет максимальное значение 255), то мы можем взять это значение в качестве нейтрального элемента нашего моноида. Но если у нас тип неограниченных целых чисел? Решение довольно простое — мы расширяем наш тип еще одним специальным значением (условно назовем его «плюс бесконечность») и зададим операцию так, чтобы выполнялись законы.
Реализуем это в коде и проверим на пустом и непустом списках
data Min a =
HighInf -- нейтральный элемент моноида (+ бесконечность)
| Min a -- упакованное значение
deriving (Eq, Ord, Show)
instance Ord a => Monoid (Min a) where
mempty = HighInf
mappend HighInf v = v
mappend v HighInf = v
mappend (Min x) (Min y) = Min $ min x y
*MyMonoid> mconcat $ map Min []
HighInf
*MyMonoid> mconcat $ map Min [5..10]
Min 5
Все как и ожидалось — минимум на пустом списке дает плюс бесконечность, на непустом — минимальный элемент.
Операция сравнения
Теперь перейдем к финальной цели — попытаемся реализовать моноид для операции сравнения. И сразу у нас возникает проблема — операция сравнения, в отличие от предыдущих рассмотренных операций, не является операцией, определенной на множестве. То есть, тип ее результата булевский, и не принадлежит типу множества ее аргументов, на которых она определена. Это бинарный предикат, а не операция. Но, как всегда, мы можем решить эту проблему с помощью введения дополнительного уровня абстракции (похоже на то, как мы делали в прошлом примере с минимумом): надо сконструировать такой тип, чтобы обобщенная операция сравнения была определена на множестве этого типа. Также нам потребуется правило трансформации значений исходного множества в этот тип и значений этого типа в булевский тип. Таким образом, обобщенное сравнение как моноидальная операция будет выглядеть так: мы переводим список исходных значений в список значений нашего типа, осуществляем свертку этого списка по моноидальной операции, и потом переводим результат в булевское значение — что и требуется от операции сравнения.
Давайте подумаем, какие значения должен предоставлять этот новый тип. Нам нужно значение нейтрального элемента, с выполнением соответствующих законов. Нам нужно значение, характеризующее ложный результат какого-либо сравнения — если у нас при свертке в цепочке моноидальных операций сравнения встретилось это значение — мы протаскиваем его до конца, игнорируя другие сравнения. И нам нужно значение, характеризующее истинный результат сравнения. Оно должно содержать в себе значение нашего исходного типа — для последующих сравнений. Но поскольку последующие сравнения могут использовать его как слева (от условного знака <), так и справа, то нам недостаточно одного значения — нам нужны крайние значения обработанного диапазона (минимальное и максимальное за всю цепочку сравнений). Таким образом, значение нашего типа будет представлять собой пару из 2 элементов, задающую свернутый диапазон. Напишем реализацию моноида и всех служебных функций:
data Asc a =
EmptyAsc -- нейтральный элемент моноида
| RangeAsc a a -- диапазон значений (сравнение истинно)
| FailAsc -- сравнение ложно
deriving (Eq, Ord, Show)
instance Ord a => Monoid (Asc a) where
mempty = EmptyAsc
mappend EmptyAsc v = v
mappend v EmptyAsc = v
mappend FailAsc v = FailAsc
mappend v FailAsc = FailAsc
mappend (RangeAsc a b) (RangeAsc c d)
| b < c = RangeAsc a d
| otherwise = FailAsc
valToAsc x = RangeAsc x x
ascToBool FailAsc = False
ascToBool _ = True
и проверим работу:
*MyMonoid> mconcat $ map valToAsc []
EmptyAsc
*MyMonoid> mconcat $ map valToAsc [3,4,7,10]
RangeAsc 3 10
*MyMonoid> mconcat $ map valToAsc [1,2,3,4,1,2]
FailAsc
*MyMonoid> isAscList []
True
*MyMonoid> isAscList [1..10]
True
*MyMonoid> isAscList $ [1,2,3,4,1,2]
False
Все работает как и требуется — наш моноид проверяет упорядоченность списка по возрастанию — то есть ровно то, что и делает аналогичная конструкция в лиспах. Нетрудно написать еще несколько аналогичных моноидов, проверяющих список на нестрогое возрастание (по операции нестрогого сравнения <=), убывание (строгое и нестрогое) и равенство всех элементов списка. Для этого достаточно только заменить соответствующий бинарный предикат в определении функции mappend.
Долгожданное заключение
Теперь я спокоен — я не обманул слушателей во время доклада :) Операция сравнения сама по себе не является моноидом, но можно ввести уровень абстракции, в котором ее обобщенный аналог будет являться таковым.
Если кому интересно — видео доклада (стрим на ютубе) Ссылки на мой гитхаб-репозиторий с реализацией интерпретаторов можно найти в моих предыдущих статьях на Хабре.