2009 → Выпуск 1

Моноиды в Haskell и их использование

(Haskell Monoids and their Uses)

Dan Piponi
(Перевод Кирилла Заборского)

Аннотация: Haskell — замечательный язык для модульного конструирования кода из небольших ортогональных друг другу блоков. Одним из таких блоков является моноид. Несмотря на то, что моноиды родом из математики (точнее, из алгебры), они применяются повсюду в программировании. На каком бы языке вы ни программировали, вы почти наверняка неявно используете один или два моноида в каждой строке кода, сами о том пока не подозревая. Используя их явно, мы находим новые способы построения кода — в частности, способы, позволяющие облегчить написание и улучшить читаемость кода.

Предлагаемая статья является введением в моноиды на Haskell. Предполагается знакомство читателя с классами типов, так как моноиды в Haskell являются классом типов. Также предполагается хотя бы поверхностное знакомство с монадами.

1  Определение моноидов

Моноид в Haskell — это тип, для которого задано правило комбинирования двух элементов этого типа для получения нового элемента этого же типа. Для задания моноида необходимо также определить нейтральный элемент, комбинирование с которым любого другого элемента даёт результат, равный этому другому элементу.

Замечательным примером являются списки. Два списка — предположим [1,2] и [3,4] — могут быть объединены оператором ++ в единый список [1,2,3,4]. Существует также пустой список [], при комбинировании с которым мы получаем второй список в неизменном виде — например, []++[1,2,3,4]==[1,2,3,4].

Другим примером является тип целых чисел Integer. Два элемента — например, 3 и 4 — могут быть скомбинированы оператором +, давая в результате сумму — 7. У нас также есть элемент 0, при сложении с которым любое целое число остаётся неизменным.

Вот пример определения класса типов Monoid:

class Monoid m where mappend :: m -> m -> m mempty :: m

Функция mappend используется для комбинирования пар элементов, а mempty представляет собой нейтральный элемент. Мы можем сделать списки моноидами, включив их в этот класс:

instance Monoid [α] where mappend = (++) mempty = []

Поскольку мы хотим, чтобы mempty не модифицировал комбинируемый с ним элемент, мы требуем, чтобы моноиды удовлеворяли следующей паре правил:

a `mappend` mempty = a

и

mempty `mappend` a = a.

Заметьте, что существует два способа скомбинировать a и b с использованием mappend. Мы можем написать a `mappend` b или b `mappend` a. От моноида не требуется совпадения результатов этих двух операций (эта тема обсуждается далее в статье), в то же время, моноиды должны обладать еще одним свойством. Предположим, у нас имеется список [3,4]. Мы хотим объединить его со списком [1,2] слева и со списком [5,6] справа. Мы можем выполнить объединение слева и получить [1,2]++[3,4], а затем сформировать ([1,2]++[3,4])++[5,6]. Мы можем также начать справа и получить [1,2]++([3,4]++[5,6]). Поскольку мы присоединяем списки с разных концов, эти операции не влияют друг на друга, и не имеет значения, которая из них выполнится первой. Это приводит нас к третьему и последнему требованию, которому должны удовлетворять моноиды:

(a `mappend` b) `mappend` c == a `mappend` (b `mappend` c)

Сформулируем это требование: «комбинирование слева и справа не мешают друг другу». Обратите внимание, что целые числа, комбинируемые операцией +, также удовлетворяют этому требованию. Это очень полезное свойство называется «ассоциативность».

Таково полное определение моноида. Haskell не принуждает к соблюдению приведенных трёх правил, но читая код, в котором присутствует моноид, мы всегда ожидаем, что эти правила соблюдены.

2  Некоторые применения моноидов

Почему нам может понадобиться использовать mappend, когда мы уже имеем в наличии такие функции, как ++ и +?

Одна из причин заключается в том, что моноиды автоматически предоставляют еще одну функцию — mconcat. Эта функция принимает на вход список значений в моноиде и комбинирует их вместе. Например, mconcat [a,b,c] будет эквивалентно a `mappend` (b `mappend` c). Таким образом, в любом моноиде существует легкий способ скомбинировать вместе целый список. Стоит отметить, что в идее mconcat заключается некоторая двусмысленность. Какой порядок должен быть выбран, чтобы вычислить mconcat [a,b,...,c,d]? Должны ли мы выполнять операции слева направо, или начать с c `mappend` d? Здесь вступает в силу правило ассоциативности: порядок не имеет значения.

Моноиды также будут к месту, если вам необходимо, чтобы ваш код был применим вне зависимости от способа комбинирования элементов. Вы можете написать код, который подобно mconcat будет работать с любым моноидом.

Явное использование класса типов Monoid в сигнатуре функции помогает читающему код понять замысел автора. Если функция имеет сигнатуру типа [α] -> β, мы знаем о ней только то, что она принимает на вход список и создаёт из него объект типа β. Внутри она может делать со списком все, что угодно. Если же мы видим функцию типа (Monoid α) => α -> β, то даже если она применяется исключительно к спискам, мы имеем примерное представление о том, что происходит со списком внутри функции. Например, мы знаем, что функция может добавить новые элементы к списку, но не удалить элемент из списка.

Один и тот же тип данных может служить основой разных моноидов. Например, как я уже упоминал, целые числа могут образовывать моноид, который определяется так:

instance Monoid Integer where mappend = (+) mempty = 0

В то же время, существует и другой естественный способ сделать моноид из целых чисел:

instance Monoid Integer where mappend = (*) mempty = 1

Мы не можем использовать оба эти определения одновременно. Поэтому библиотека Data.Monoid не создаёт моноид напрямую из Integer. Вместо этого, она оборачивает его в Sum (сумму) и Product (произведение). К тому же, библиотека делает это в более общем виде, позволяя превратить любые типы из класса Num в один из двух видов моноидов:

Num α => Monoid (Sum α)

и

Num α => Monoid (Product α)

Чтобы воспользоваться описанными функциями моноида, необходимо представить наши данные соответствующим образом. Например, mconcat [Sum 2, Sum 3, Sum 4] — это Sum 9, в то время как mconcat [Product 2, Product 3, Product 4] — это Product 24.

Использование Sum и Product кажется явным усложнением обычных операций сложения и умножения. Зачем же так делать?

3  Монада Writer

Моноиды можно представлять как накопители. Имея промежуточную сумму n и текущее значение a, мы можем получить новую промежуточную сумму n' = n `mappend` a. Накопление итогов часто применяется в программировании, поэтому остановимся на этой идее подробнее. Монада Writer предназначена специально для этого. Мы можем написать монадический код, который в качестве «побочного эффекта»будет накапливать некоторые значения. Функция, выполняющая накопление, называется несколько странно — tell. Следующий пример демонстрирует реализацию трассировки совершаемых действий.

import Data.Monoid import Data.Foldable import Control.Monad.Writer import Control.Monad.State fact1 :: Integer -> Writer String Integer fact1 0 = return 1 fact1 n = do let n' = n-1 tell $ "We've taken one away from " ++ show n ++ "\n" m <- fact1 n' tell $ "We've called f " ++ show m ++ "\n" let r = n * m tell $ "We've multiplied " ++ show n ++ " and " ++ show m ++ "\n" return r

В этом примере реализована функция вычисления факториала, сообщающая нам о выполняемых вычислениях. Каждый раз, когда вызывается функция tell, мы комбинируем её аргумент с промежуточным журналом вычислений, который был накоплен в результате предыдущих вызовов этой функции. Для извлечения журнала мы используем runWriter. Запустив следующий код:

ex1 = runWriter (fact1 10)

мы получаем значение 10!, а вместе с ним — список шагов, которые потребовались для вычисления этого значения.

Writer позволяет накапливать не только строки. Мы можем использовать эту монаду с любым моноидом. Например, мы можем использовать её для подсчета количества операций сложения и умножения, необходимых для вычисления факториала числа. Для этого мы должны передать в tell значение соответствующего типа. В данном случае мы будем складывать значения, воспользовавшись моноидом для сложения — Sum. Мы можем написать:

fact2 :: Integer -> Writer (Sum Integer) Integer fact2 0 = return 1 fact2 n = do let n' = n-1 tell $ Sum 1 m <- fact2 n' let r = n * m tell $ Sum 1 return r ex2 = runWriter (fact2 10)

Эту задачу мы могли бы выполнить другим способом, примененив монаду State:

fact3 :: Integer -> State Integer Integer fact3 0 = return 1 fact3 n = do let n' = n-1 modify (+1) m <- fact3 n' let r = n * m modify (+1) return r ex3 = runState (fact3 10) 0

Результат такой реализации идентичен предыдущему, но версия с использованием Writer имеет большое преимущество. Из её типа — f :: Integer -> Writer (Sum Integer) Integer — можно сразу понять, что наша функция имеет побочный эффект, заключающийся в аддитивном накопении некоторого целого числа. Мы точно знаем, что она не перемножает накапливаемые значения. Не прочитав ни одной строчки кода функции, мы можем понять, что происходит у неё внутри, благодаря информации, содержащейся в её типе. Версия реализации функции, использующая State, вольна делать с накапливаемым значением все, что угодно, поэтому её назначение понять сложнее.

Data.Monoid также даёт нам моноид Any. Это тип Bool с заданной на нем операцией дизъюнкции, более известной как ||. Такое название дано специально, чтобы показать, что при комбинировании любого набора элементов типа Any, наличие в наборе элемента со значением «истина» (Any True) даёт результат, выражающийся как «некоторый элемент является истинным» (Any True). Таким образом, мы получаем своего рода односторонний переключатель. Мы начинаем накопление с memempty, то есть Any False, что соответствует выключенному положению переключателя. Как только к нашему промежуточному результату добавляется значение Any True, переключатель переводится во включенное состояние. Вне зависимости от того, какие значения будут добавлены позже, переключатель уже не выключится. Этот процесс соответствует часто используемому в программировании шаблону: флаг, который в качестве побочного эффекта включается в случае выполнения некоторого условия.

fact4 :: Integer -> Writer Any Integer fact4 0 = return 1 fact4 n = do let n' = n-1 m <- fact4 n' let r = n * m tell (Any (r==120)) return r ex4 = runWriter (fact4 10)

В приведенном выше примере по окончании вычисления мы получаем значение n!, при этом нам также сообщается, если в процессе вычисления было выполнено умножение, результат которого был равен 120. Вызов функции tell практически повторяет словесное описание задачи на английском языке: «сообщи вызвавшему меня, если значение r когда-либо станет равно 120». Помимо того, что реализация этого флага требует минимального количества кода, существует еще одно преимущество. Достаточно взглянуть на тип этой версии функции, чтобы понять, что в ней происходит. Мы сразу видим, что эта функция в качестве побочного эффекта вычисляет флаг, который может включиться, но не может быть выключен. Для сигнатуры типа это большой объем информации. Во многих других языках программирования мы можем встретить булевый тип в сигнатуре, но нам придётся читать код, чтобы понять, как именно он используется.

4  Коммутативные моноиды, некоммутативные моноиды и дуальные моноиды

Говорят, что два элемента моноида x и y можно поменять местами, если x `mappend` y == y `mappend` x. Моноид называется коммутативным, если все его элементы можно менять местами. Хорошим примером коммутативного моноида является тип целых чисел. Для любой пары целых чисел a+b == b+a.

Если моноид не является коммутативным, то его называют некоммутативным. Если он некоммутативен, то существует пара элементов x и y, для которой x `mappend` y не равно y `mappend` x, и следовательно функции mappend и flip mappend не равнозначны. Например, [1,2]++[3,4] отличается от [3,4]++ [1,2]. Интересным следствием этой особенности является то, что мы можем создать другой моноид, в котором функцией комбинирования будет flip mappend. Мы по-прежнему можем использовать тот же элемент mempty, таким образом два первых правила для моноидов будут соблюдаться. Будет неплохим упражнением доказать, что и третье правило при этом также будет выполнено. Такой «перевёрнутый» моноид называется дуальным, и Data.Monoid предоставляет конструктор типов Dual для построения дуальных моноидов. Он может быть использован для инвертирования порядка накопления данных монадой Writer. К примеру, следующий код собирает трассировку выполненных действий в обратном порядке:

fact5 :: Integer -> Writer (Dual String) Integer fact5 0 = return 1 fact5 n = do let n' = n-1 tell $ Dual $ "We've taken one away from " ++ show n ++ "\n" m <- fact5 n' tell $ Dual $ "We've called f " ++ show m ++ "\n" let r = n * m tell $ Dual $ "We've multiplied " ++ show n ++ " and " ++ show m ++ "\n" return r ex5 = runWriter (fact5 10)

5  Произведение моноидов

Предположим, что мы хотим получать два побочных эффекта одновременно. Например, мы хотим вести подсчет числа выполняемых инструкций, а также получать словесную трассировку всех вычислений. Для комбинирования двух монад Writer мы могли бы воспользоваться преобразователями монад, но есть способ проще — мы можем скомбинировать два моноида в «произведение» моноидов. Определяется оно следующим образом:

instance (Monoid α, Monoid β) => Monoid (α, β) where mempty = (mempty, mempty) mappend (u,v) (w,x) = (u `mappend` w, v `mappend` x)

Каждый раз, применяя mappend к произведению, мы на самом деле применяем пару mappend отдельно к каждому элементу пары. С помощью следующих вспомогательных функций:

tellFst a = tell $ (a, mempty) tellSnd b = tell $ (mempty, b)

мы можем использовать два моноида одновременно:

tellFst a = tell $ (a, mempty) fact6 :: Integer -> Writer (String, Sum Integer) Integer fact6 0 = return 1 fact6 n = do let n' = n-1 tellSnd (Sum 1) tellFst $ "We've taken one away from " ++ show n ++ "\n" m <- fact6 n' let r = n * m tellSnd (Sum 1) tellFst $ "We've multiplied " ++ show n ++ " and " ++ show m ++ "\n" return r ex6 = runWriter (fact6 5)

Если бы мы имплементировали наш код с использованием одного специфического моноида, скажем, моноида для списков, применимость нашего кода была бы очень ограничена. Используя же обобщённый класс типов Monoid, мы обеспечиваем возможность повторного использования не только отдельных моноидов из нашего кода, но и наборов моноидов. Это способствует эффективности кода, поскольку мы можем собирать различные значения за один обход структуры данных. При этом мы обеспечиваем читаемость кода — наши алгоритмы легко читаются, поскольку код использует интерфейс к единственному моноиду.

6  «Сворачиваемые» данные

Последним примером применения моноидов в данной статье будет библиотека Data.Foldable. Она предоставляет обобщённый подход к обходу структур данных и сборке необходимых значений в процессе. Функция foldMap применяет соответствующую функцию к каждому элементу структуры и собирает результаты. Ниже следует пример реализации foldMap для деревьев:

data Tree α = Empty | Leaf α | Node (Tree α) α (Tree α) instance Foldable Tree where foldMap f Empty = mempty foldMap f (Leaf x) = f x foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r

Теперь мы можем использовать любой из рассмотренных выше моноидов для вычисления свойств деревьев. Например, мы можем использовать функцию (==1) для проверки равенства каждого элемента единице или использовать моноид Any, чтобы выяснить, существует ли в дереве элемент, равный единице. Вот пара примеров: один выясняет, существует ли в дереве элемент, равный 1, а другой — проверяет, каждый ли элемент дерева имеет значение больше 5.

tree = Node (Leaf 1) 7 (Leaf 2) ex7 = foldMap (Any . (== 1)) tree ex8 = foldMap (All . (> 5)) tree

Заметьте, что эти выражения без изменений могут быть использованы с любым сворачиваемым типом, не только с деревьями.

Надеюсь, вы согласитесь, что наши намерения представлены в коде в удобной для прочтения форме.

Тут же напрашивается еще одно упражнение: напишите подобный код для нахождения минимального и максимального элемента дерева. Для этого вам может понадобиться сконструировать новый моноид наподобие Any или All. Попробуйте найти оба элемента за один обход дерева, используя произведение моноидов.

Пример со «сворачиваемыми» данными иллюстрирует еще один момент. Программисту, реализующему foldMap для дерева, нет нужды заботиться о том, должно ли левое поддерево присоединяться к центральному элементу до правого или после. Ассоциативность гарантирует, что функция даст одинаковый результат вне зависимости от способа.

7  Заключение

Моноиды предоставляют общий подход к комбинированию и сбору значений. Они позволяют нам писать такой код, для которого неважно, каким образом мы комбинируем значения, что делает его более удобным для повторного использования. Используя именованные моноиды, мы можем указывать сингатуры типов так, чтобы читающим код были понятны наши намерения: например, используя Any вместо Bool, мы поясняем, как именно будет использовано булево значение. Мы можем комбинировать основанные на моноидах блоки, предоставляемые библиотеками Haskell, для построения полезных и легко читаемых алгоритмов с минимумом усилий.

Заключительные заметки: математики часто называют mappend «бинарным оператором» или «умножением». Так же как и в обычной алгебре, его часто записывают знаком умножения (a × b) или даже слитно (ab). Подробнее о моноидах можно прочитать на Википедии [3]. К сожалению, у меня не хватает времени написать о морфизмах моноидов, о том, почему списочные моноиды являются свободными1 (и какие возможности это даёт при написании кода), а также как альфа-композиция изображений выражается в моноидах, и о многом другом.

Список литературы

[1]
Control.Monad.Writer.Lazy. Online документация к GHC, http://hackage.haskell.org/packages/archive/mtl/latest/doc/html/Control-Monad-Writer-Lazy.html.
[2]
Data.Monoid. Online документация к GHC, http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Monoid.html.
[3]
Monoid. Статья в Wikipedia, http://en.wikipedia.org/wiki/Monoid.
[4]
Brian Hurt. Random thoughts on haskell. Запись в блоге, http://enfranchisedmind.com/blog/posts/random-thoughts-on-haskell/.
[5]
Mark P. Jones. Functional programming with overloading and higher-order polymorphism, 1995.
1
О том, что такое свободные моноиды, смотрите определение в Википедии: http://en.wikipedia.org/wiki/Free_monoid Прим. пер.
Этот документ был получен из LATEX при помощи HEVEA