Моноид Ordering

Помните тип Ordering? Он используется в качестве результата при сравнении сущностей и может иметь три значения: LT, EQ и GT, которые соответственно означают «меньше, чем», «равно» и «больше, чем».

ghci> 1 `compare` 2

ghci> 2 `compare` 2

ghci> 3 `compare` 2

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

instance Monoid Ordering where

mempty = EQ

LT `mappend` _ = LT

EQ `mappend` y = y

GT `mappend` _ = GT

Экземпляр определяется следующим образом: когда мы объединяем два значения типа Ordering с помощью функции mappend, сохраняется значение слева, если значение слева не равно EQ. Если значение слева равно EQ, результатом будет значение справа. Единичным значением является EQ. На первый взгляд, такой выбор может показаться несколько случайным, но на самом деле он имеет сходство с тем, как мы сравниваем слова в алфавитном порядке. Мы смотрим на первые две буквы, и, если они отличаются, уже можем решить, какое слово шло бы первым в словаре. Если же первые буквы равны, то мы переходим к сравнению следующей пары букв, повторяя процесс[13].

Например, сравнивая слова «ox» и «on», мы видим, что первые две буквы каждого слова равны, а затем продолжаем сравнивать вторые буквы. Поскольку «x» в алфавите идёт после «n», мы знаем, в каком порядке должны следовать эти слова. Чтобы лучше понять, как EQ является единичным значением, обратите внимание, что если бы мы втиснули одну и ту же букву в одну и ту же позицию в обоих словах, их расположение друг относительно друга в алфавитном порядке осталось бы неизменным; к примеру, слово «oix» будет по-прежнему идти следом за «oin».

Важно, что в экземпляре класса Monoid для типа Ordering выражение x `mappend` y не равно выражению y `mappend` x. Поскольку первый параметр сохраняется, если он не равен EQ, LT `mappend` GT в результате вернёт LT, тогда как GT `mappend` LT в результате вернёт GT:

ghci> LT `mappend` GT

ghci> GT `mappend` LT

ghci> mempty `mappend` LT

ghci> mempty `mappend` GT

Хорошо, так чем же этот моноид полезен? Предположим, мы пишем функцию, которая принимает две строки, сравнивает их длину и возвращает значение типа Ordering. Но если строки имеют одинаковую длину, то вместо того, чтобы сразу вернуть значение EQ, мы хотим установить их расположение в алфавитном порядке.

Вот один из способов это записать:

lengthCompare :: String –> String –> Ordering

lengthCompare x y = let a = length x `compare` length y

b = x `compare` y

in if a == EQ then b else a

Результат сравнения длин мы присваиваем образцу a, результат сравнения по алфавиту – образцу b; затем, если оказывается, что длины равны, возвращаем их порядок по алфавиту.

Но, имея представление о том, что тип Ordering является моноидом, мы можем переписать эту функцию в более простом виде:

import Data.Monoid

lengthCompare :: String –> String –> Ordering

lengthCompare x y = (length x `compare` length y) `mappend`(x `compare` y)

Давайте это опробуем:

ghci> lengthCompare "ямб" "хорей"

ghci> lengthCompare "ямб" "хор"

Вспомните, что когда мы используем функцию mappend, сохраняется её левый параметр, если он не равен значению EQ; если он равен EQ, сохраняется правый. Вот почему мы поместили сравнение, которое мы считаем первым, более важным критерием, в качестве первого параметра. Теперь предположим, что мы хотим расширить эту функцию, чтобы она также сравнивала количество гласных звуков, и установить это вторым по важности критерием для сравнения. Мы изменяем её вот так:

import Data.Monoid

lengthCompare :: String –> String –> Ordering

lengthCompare x y = (length x `compare` length y) `mappend`

(vowels x `compare` vowels y) `mappend`

(x `compare` y)

where vowels = length . filter (`elem` "аеёиоуыэюя")

Мы создали вспомогательную функцию, которая принимает строку и сообщает нам, сколько она содержит гласных звуков, сначала отфильтровывая в ней только буквы, находящиеся в строке "аеёиоуыэюя", а затем применяя функцию length.

ghci> lengthCompare "ямб" "абыр"

ghci> lengthCompare "ямб" "абы"

ghci> lengthCompare "ямб" "абр"

В первом примере длины оказались различными, поэтому вернулось LT, так как длина слова "ямб" меньше длины слова "абыр". Во втором примере длины равны, но вторая строка содержит больше гласных звуков, поэтому опять возвращается LT. В третьем примере они обе имеют одинаковую длину и одинаковое количество гласных звуков, поэтому сравниваются по алфавиту, и слово "ямб" выигрывает.

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