Изучай Haskell во имя добра!

Липовача Миран

12

Моноиды

 

 

В этой главе представлен ещё один полезный и интересный класс типов Monoid. Он существует для типов, значения которых могут быть объединены при помощи бинарной операции. Мы рассмотрим, что именно представляют собой моноиды и что утверждают их законы. Затем рассмотрим некоторые моноиды в языке Haskell и обсудим, как они могут нам пригодиться.

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

 

Оборачивание существующего типа в новый тип

 

Пока что вы научились создавать свои алгебраические типы данных, используя ключевое слово data. Вы также увидели, как можно давать синонимы имеющимся типам с применением ключевого слова type. В этом разделе мы рассмотрим, как создаются новые типы на основе имеющихся типов данных с использованием ключевого слова newtype. И в первую очередь, конечно, поговорим о том, чем всё это может быть нам полезно.

В главе 11 мы обсудили пару способов, при помощи которых списковый тип может быть аппликативным функтором. Один из этих способов состоит в том, чтобы заставить оператор <*> брать каждую функцию из списка, являющегося его левым параметром, и применять её к каждому значению в списке, который находится справа, что в результате возвращает все возможные комбинации применения функции из левого списка к значению в правом:

ghci> [(+1),(*100),(*5)] <*> [1,2,3]

[2,3,4,100,200,300,5,10,15]

Второй способ заключается в том, чтобы взять первую функцию из списка слева от оператора <*> и применить её к первому значению справа, затем взять вторую функцию из списка слева и применить её ко второму значению справа, и т. д. В конечном счёте получается нечто вроде застёгивания двух списков.

Но списки уже имеют экземпляр класса Applicative, поэтому как нам определить для списков второй экземпляр класса Applicative? Как вы узнали, для этой цели был введён тип ZipList a. Он имеет один конструктор данных ZipList, у которого только одно поле. Мы помещаем оборачиваемый нами список в это поле. Далее для типа ZipList определяется экземпляр класса Applicative, чтобы, когда нам понадобится использовать списки в качестве аппликативных функторов для застёгивания, мы могли просто обернуть их с по мощью конструктора ZipList. Как только мы закончили, разворачиваем их с помощью getZipList:

ghci> getZipList $ ZipList [(+1),(*100),(*5)] <*> ZipList [1,2,3]

[2,200,15]

Итак, какое отношение это имеет к ключевому слову newtype? Хорошо, подумайте, как бы мы могли написать объявление data для нашего типа ZipList a! Вот один из способов:

data ZipList a = ZipList [a]

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

data ZipList a = ZipList { getZipList :: [a] }

Это прекрасно смотрится и на самом деле работает очень хорошо. У нас было два способа сделать существующий тип экземпляром класса типов, поэтому мы использовали ключевое слово data, чтобы просто обернуть этот тип в другой, и сделали другой тип экземпляром вторым способом.

Ключевое слово newtype в языке Haskell создано специально для тех случаев, когда мы хотим просто взять один тип и обернуть его во что-либо, чтобы представить его как другой тип. В существующих сейчас библиотеках тип ZipList a определён вот так:

newtype ZipList a = ZipList { getZipList :: [a] }

Вместо ключевого слова data используется newtype. Теперь разберёмся, почему. Ну, к примеру, декларация newtype быстрее. Если вы используете ключевое слово data для оборачивания типа, появляются «накладные расходы» на все эти оборачивания и разворачивания, когда ваша программа выполняется. Но если вы воспользовались ключевым словом newtype, язык Haskell знает, что вы просто применяете его для оборачивания существующего типа в новый тип (отсюда название), поскольку хотите, чтобы внутренне он остался тем же, но имел иной тип. По этой причине язык Haskell может избавиться от оборачивания и разворачивания, как только решит, какое значение какого типа.

Так почему бы всегда не использовать newtype вместо data? Когда вы создаёте новый тип из имеющегося типа, используя ключевое слово newtype, у вас может быть только один конструктор значения, который имеет только одно поле. Но с помощью ключевого слова data вы можете создавать типы данных, которые имеют несколько конструкторов значения, и каждый конструктор может иметь ноль или более полей:

data Profession = Fighter | Archer | Accountant

data Race = Human | Elf | Orc | Goblin

data PlayerCharacter = PlayerCharacter Race Profession

При использовании ключевого слова newtype мы можем использовать ключевое слово deriving – точно так же, как мы бы делали это с декларацией data. Мы можем автоматически порождать экземпляры для классов Eq, Ord, Enum, Bounded, Show и Read. Если мы породим экземпляр для класса типа, то оборачиваемый нами тип уже должен иметь экземпляр для данного класса типов. Это логично, поскольку ключевое слово newtype всего лишь оборачивает существующий тип. Поэтому теперь мы сможем печатать и сравнивать значения нашего нового типа, если сделаем следующее:

newtype CharList = CharList { getCharList :: [Char] } deriving (Eq, Show)

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

ghci> CharList "Вот что мы покажем!"

CharList {getCharList = "Вот что мы покажем!"}

ghci> CharList "бенни" == CharList "бенни"

True

ghci> CharList "бенни" == CharList "устрицы"

False

В данном конкретном случае использования ключевого слова newtype конструктор данных имеет следующий тип:

CharList :: [Char] –> CharList

Он берёт значение типа [Char] и возвращает значение типа CharList. Из предыдущих примеров, где мы использовали конструктор данных CharList, видно, что действительно так оно и есть. И наоборот, функция getCharList, которая была автоматически сгенерирована за нас (потому как мы использовали синтаксис записей с именованными полями в нашей декларации newtype), имеет следующий тип:

getCharList :: CharList –> [Char]

Она берёт значение типа CharList и преобразует его в значение типа [Char]. Вы можете воспринимать это как оборачивание и разворачивание, но также можете рассматривать это как преобразование значений из одного типа в другой.

 

Использование ключевого слова newtype для создания экземпляров классов типов

Часто мы хотим сделать наши типы экземплярами определённых классов типов, но параметры типа просто не соответствуют тому, что нам требуется. Сделать для типа Maybe экземпляр класса Functor легко, потому что класс типов Functor определён вот так:

class Functor f where

   fmap :: (a -> b) -> f a -> f b

Поэтому мы просто начинаем с этого:

instance Functor Maybe where

А потом реализуем функцию fmap.

Все параметры типа согласуются, потому что тип Maybe занимает место идентификатора f в определении класса типов Functor. Если взглянуть на функцию fmap, как если бы она работала только с типом Maybe, в итоге она ведёт себя вот так:

fmap :: (a -> b) -> Maybe a -> Maybe b

Разве это не замечательно? Ну а что если мы бы захотели определить экземпляр класса Functor для кортежей так, чтобы при отображении кортежа с помощью функции fmap входная функция применялась к первому элементу кортежа? Таким образом, выполнение fmap (+3) (1,1) вернуло бы (4,1). Оказывается, что написание экземпляра для этого отчасти затруднительно. При использовании типа Maybe мы просто могли бы написать: instance Functor Maybe where, так как только для конструкторов типа, принимающих ровно один параметр, могут быть определены экземпляры класса Functor. Но, похоже, нет способа сделать что-либо подобное при использовании типа (a,b) так, чтобы в итоге изменялся только параметр типа a, когда мы используем функцию fmap. Чтобы обойти эту проблему, мы можем сделать новый тип из нашего кортежа с помощью ключевого слова newtype так, чтобы второй параметр типа представлял тип первого компонента в кортеже:

newtype Pair b a = Pair { getPair :: (a, b) }

А теперь мы можем определить для него экземпляр класса Functor так, чтобы функция отображала первый компонент:

instance Functor (Pair c) where

   fmap f (Pair (x, y)) = Pair (f x, y)

Как видите, мы можем производить сопоставление типов, объявленных через декларацию newtype, с образцом. Мы производим сопоставление, чтобы получить лежащий в основе кортеж, применяем функцию f к первому компоненту в кортеже, а потом используем конструктор значения Pair, чтобы преобразовать кортеж обратно в значение типа Pair b a. Если мы представим, какого типа была бы функция fmap, если бы она работала только с нашими новыми парами, получится следующее:

fmap :: (a –> b) –> Pair c a –> Pair c b

Опять-таки, мы написали instance Functor (Pair c) where, и поэтому конструктор Pair c занял место идентификатора f в определении класса типов для Functor:

class Functor f where

   fmap :: (a -> b) -> f a -> f b

Теперь, если мы преобразуем кортеж в тип Pair b a, можно будет использовать с ним функцию fmap, и функция будет отображать первый компонент:

ghci> getPair $ fmap (*100) (Pair (2, 3))

(200,3)

ghci> getPair $ fmap reverse (Pair ("вызываю лондон", 3))

("ноднол юавызыв",3)

 

О ленивости newtype

Единственное, что можно сделать с помощью ключевого слова newtype, – это превратить имеющийся тип в новый тип, поэтому внутренне язык Haskell может представлять значения типов, определённых с помощью декларации newtype, точно так же, как и первоначальные, зная в то же время, что их типы теперь различаются. Это означает, что декларация newtype не только зачастую быстрее, чем data, – её механизм сопоставления с образцом ленивее. Давайте посмотрим, что это значит.

Как вы знаете, язык Haskell по умолчанию ленив, что означает, что какие-либо вычисления будут иметь место только тогда, когда мы пытаемся фактически напечатать результаты выполнения наших функций. Более того, будут произведены только те вычисления, которые необходимы, чтобы наша функция вернула нам результаты. Значение undefined в языке Haskell представляет собой ошибочное вычисление. Если мы попытаемся его вычислить (то есть заставить Haskell на самом деле произвести вычисление), напечатав его на экране, то в ответ последует настоящий припадок гнева – в технической терминологии он называется исключением:

ghci> undefined

*** Exception: Prelude.undefined

А вот если мы создадим список, содержащий в себе несколько значений undefined, но запросим только «голову» списка, которая не равна undefined, всё пройдёт гладко! Причина в том, что языку Haskell не нужно вычислять какие-либо из остальных элементов в списке, если мы хотим посмотреть только первый элемент. Вот пример:

ghci> head [3,4,5,undefined,2,undefined]

3

Теперь рассмотрите следующий тип:

data CoolBool = CoolBool { getCoolBool :: Bool }

Это ваш обыкновенный алгебраический тип данных, который был объявлен с использованием ключевого слова data. Он имеет один конструктор данных, который содержит одно поле с типом Bool. Давайте создадим функцию, которая сопоставляет с образцом значение CoolBool и возвращает значение "привет" вне зависимости от того, было ли значение Bool в CoolBool равно True или False:

helloMe :: CoolBool –> String helloMe (CoolBool _) = "привет"

Вместо того чтобы применять эту функцию к обычному значению типа CoolBool, давайте сделаем ей обманный бросок – применим её к значению undefined!

ghci> helloMe undefined

*** Exception: Prelude.undefined

Тьфу ты! Исключение! Почему оно возникло? Типы, определённые с помощью ключевого слова data, могут иметь много конструкторов данных(хотя CoolBool имеет только один конструктор). Поэтому для того чтобы понять, согласуется ли значение, переданное нашей функции, с образцом (CoolBool _), язык Haskell должен вычислить значение ровно настолько, чтобы понять, какой конструктор данных был использован, когда мы создавали значение. И когда мы пытаемся вычислить значение undefined, будь оно даже небольшим, возникает исключение.

Вместо ключевого слова data для CoolBool давайте попробуем использовать newtype:

newtype CoolBool = CoolBool { getCoolBool :: Bool }

Нам не нужно изменять нашу функцию helloMe, поскольку синтаксис сопоставления с образцом одинаков независимо от того, использовалось ли ключевое слово newtype или data для объявления вашего типа. Давайте сделаем здесь то же самое и применим helloMe к значению undefined:

ghci> helloMe undefined

"привет"

Сработало! Хм-м-м, почему? Ну, как вы уже узнали, когда вы используете ключевое слово newtype, язык Haskell внутренне может представлять значения нового типа таким же образом, как и первоначальные значения. Ему не нужно помещать их ещё в одну коробку; он просто должен быть в курсе, что значения имеют разные типы. И поскольку язык Haskell знает, что типы, созданные с помощью ключевого слова newtype, могут иметь лишь один конструктор данных и одно поле, ему не нужно вычислять значение, переданное функции, чтобы убедиться, что значение соответствует образцу (CoolBool _).

Это различие в поведении может казаться незначительным, но на самом деле оно очень важно. Оно показывает, что хотя типы, определённые с помощью деклараций data и newtype, ведут себя одинаково с точки зрения программиста (так как оба имеют конструкторы данных и поля), это фактически два различных механизма. Тогда как ключевое слово data может использоваться для создания ваших новых типов с нуля, ключевое слово newtype предназначено для создания совершенно нового типа из существующего. Сравнение значений деклараций newtype с образцом не похоже на вынимание содержимого коробки (что характерно для деклараций data); это скорее представляет собой прямое преобразование из одного типа в другой.

 

Ключевое слово type против newtype и data

К этому моменту, возможно, вы с трудом улавливаете различия между ключевыми словами type, data и newtype. Поэтому давайте немного повторим пройденное.

Ключевое слово type предназначено для создания синонимов типов. Мы просто даём другое имя уже существующему типу, чтобы на этот тип было проще сослаться. Скажем, мы написали следующее:

type IntList = [Int]

Всё, что это нам даёт, – возможность сослаться на тип [Int] как IntList. Их можно использовать взаимозаменяемо. Мы не получаем конструктор данных IntList или что-либо в этом роде. Поскольку идентификаторы [Int] и IntList являются лишь двумя способами сослаться на один и тот же тип, неважно, какое имя мы используем в наших аннотациях типов:

ghci> ([1,2,3] :: IntList) ++ ([1,2,3] :: [Int])

[1,2,3,1,2,3]

Мы используем синонимы типов, когда хотим сделать наши сигнатуры типов более наглядными. Мы даём типам имена, которые говорят нам что-либо об их предназначении в контексте функций, где они используются. Например, когда мы использовали ассоциативный список типа [(String,String)] для представления телефонной книги в главе 7, то дали ему синоним типа PhoneBook, чтобы сигнатуры типов наших функций легко читались.

Ключевое слово newtype предназначено для оборачивания существующих типов в новые типы – в основном чтобы для них можно было проще определить экземпляры некоторых классов типов. Когда мы используем ключевое слово newtype для оборачивания существующего типа, получаемый нами тип отделён от исходного. Предположим, мы определяем следующий тип при помощи декларации newtype:

newtype CharList = CharList { getCharList :: [Char] }

Нельзя использовать оператор ++, чтобы соединить значение типа CharList и список типа [Char]. Нельзя даже использовать оператор ++, чтобы соединить два значения типа CharList, потому что оператор ++ работает только со списками, а тип CharList не является списком, хотя можно сказать, что CharList содержит список. Мы можем, однако, преобразовать два значения типа CharList в списки, соединить их с помощью оператора ++, а затем преобразовать получившееся обратно в CharList.

Когда в наших объявлениях типа newtype мы используем синтаксис записей с именованными полями, то получаем функции для преобразования между новым типом и изначальным типом – а именно конструктор данных нашего типа newtype и функцию для извлечения значения из его поля. Для нового типа также автоматически не определяются экземпляры классов типов, для которых есть экземпляры исходного типа, поэтому нам необходимо их сгенерировать (ключевое слово deriving) либо определить вручную.

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

Ключевое слово data предназначено для создания ваших собственных типов данных. Ими вы можете увлечься не на шутку. Они могут иметь столько конструкторов и полей, сколько вы пожелаете, и использоваться для реализации любого алгебраического типа данных – всего, начиная со списков и Maybe-подобных типов и заканчивая деревьями.

Подведём итог вышесказанному. Используйте ключевые слова следующим образом:

• если вы просто хотите, чтобы ваши сигнатуры типов выглядели понятнее и были более наглядными, вам, вероятно, нужны синонимы типов;

• если вы хотите взять существующий тип и обернуть его в новый, чтобы определить для него экземпляр класса типов, скорее всего, вам пригодится newtype;

• если вы хотите создать что-то совершенно новое, есть шанс, что вам поможет ключевое слово data.

 

В общих чертах о моноидах

 

Классы типов в языке Haskell используются для представления интерфейса к типам, которые обладают неким схожим поведением. Мы начали с простых классов типов вроде класса Eq, предназначенного для типов, значения которых можно сравнить, и класса Ord – для сущностей, которые можно упорядочить. Затем перешли к более интересным классам типов, таким как классы Functor и Applicative.

Создавая тип, мы думаем о том, какие поведения он поддерживает (как он может действовать), а затем решаем, экземпляры каких классов типов для него определить, основываясь на необходимом нам поведении. Если разумно, чтобы значения нашего типа были сравниваемыми, мы определяем для нашего типа экземпляр класса Eq. Если мы видим, что наш тип является чем-то вроде функтора – определяем для него экземпляр класса Functor, и т. д.

Теперь рассмотрим следующее: оператор * – это функция, которая принимает два числа и перемножает их. Если мы умножим какое-нибудь число на 1, результат всегда равен этому числу. Неважно, выполним ли мы 1 * x или x * 1 – результат всегда равен x. Аналогичным образом оператор ++ – это функция, которая принимает две сущности и возвращает третью. Но вместо того, чтобы перемножать числа, она принимает два списка и конкатенирует их. И так же, как оператор *, она имеет определённое значение, которое не изменяет другое значение при использовании с оператором ++. Этим значением является пустой список: [].

ghci> 4 * 1

4

ghci> 1 * 9

9

ghci> [1,2,3] ++ []

[1,2,3]

ghci> [] ++ [0.5, 2.5]

[0.5,2.5]

Похоже, что оператор * вместе с 1 и оператор ++ наряду с [] разделяют некоторые общие свойства:

• функция принимает два параметра;

• параметры и возвращаемое значение имеют одинаковый тип;

• существует такое значение, которое не изменяет другие значения, когда используется с бинарной функцией.

Есть и ещё нечто общее между двумя этими операциями, хотя это может быть не столь очевидно, как наши предыдущие наблюдения. Когда у нас есть три и более значения и нам необходимо использовать бинарную функцию для превращения их в один результат, то порядок, в котором мы применяем бинарную функцию к значениям, неважен. Например, независимо от того, выполним ли мы (3 * 4) * 5 или 3 * (4 * 5), результат будет равен 60. То же справедливо и для оператора ++:

ghci> (3 * 2) * (8 * 5)

240

ghci> 3 * (2 * (8 * 5))

240

ghci> "ой" ++ ("лю" ++ "ли")

"ойлюли"

ghci> ("ой" ++ "лю") ++ "ли"

"ойлюли"

Мы называем это свойство ассоциативностью. Оператор * ассоциативен, оператор ++ тоже. Однако оператор –, например, не ассоциативен, поскольку выражения (5 – 3) – 4 и 5 – (3 – 4) возвращают различные результаты.

Зная об этих свойствах, мы наконец-то наткнулись на моноиды!

 

Класс типов Monoid

Моноид состоит из ассоциативной бинарной функции и значения, которое действует как единица (единичное или нейтральное значение) по отношению к этой функции. Когда что-то действует как единица по отношению к функции, это означает, что при вызове с данной функцией и каким-то другим значением результат всегда равен этому другому значению. Значение 1 является единицей по отношению к оператору *, а значение [] является единицей по отношению к оператору ++. В мире языка Haskell есть множество других моноидов, поэтому существует целый класс типов Monoid. Он предназначен для типов, которые могут действовать как моноиды. Давайте посмотрим, как определён этот класс типов:

class Monoid m where

   mempty :: m

   mappend :: m –> m –> m mconcat :: [m] –> m

   mconcat = foldr mappend mempty

Класс типов Monoid определён в модуле Data.Monoid. Давайте потратим некоторое время, чтобы как следует с ним познакомиться.

Прежде всего, нам видно, что экземпляры класса Monoid могут быть определены только для конкретных типов, потому что идентификатор m в определении класса типов не принимает никаких параметров типа. В этом состоит отличие от классов Functor и Applicative, которые требуют, чтобы их экземплярами были конструкторы типа, принимающие один параметр.

Первой функцией является mempty. На самом деле это не функция, поскольку она не принимает параметров. Это полиморфная константа вроде minBound из класса Bounded. Значение mempty представляет единицу для конкретного моноида.

Далее, у нас есть функция mappend, которая, как вы уже, наверное, догадались, является бинарной. Она принимает два значения одного типа и возвращает ещё одно значение того же самого типа. Решение назвать так функцию mappend было отчасти неудачным, поскольку это подразумевает, что мы в некотором роде присоединяем два значения. Тогда как оператор ++ действительно принимает два списка и присоединяет один в конец другого, оператор * на самом деле не делает какого-либо присоединения – два числа просто перемножаются. Когда вы встретите другие экземпляры класса Monoid, вы поймёте, что большинство из них тоже не присоединяют значения. Поэтому избегайте мыслить в терминах присоединения; просто рассматривайте mappend как бинарную функцию, которая принимает два моноидных значения и возвращает третье.

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

 

Законы моноидов

Прежде чем перейти к более конкретным экземплярам класса Monoid, давайте кратко рассмотрим законы моноидов.

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

• mempty `mappend` x = x

• x `mappend` mempty = x

• (x `mappend` y) `mappend` z = x `mappend` (y `mappend` z)

Первые два закона утверждают, что значение mempty должно вести себя как единица по отношению к функции mappend, а третий говорит, что функция mappend должна быть ассоциативна (порядок, в котором мы используем функцию mappend для сведения нескольких моноидных значений в одно, не имеет значения). Язык Haskell не проверяет определяемые экземпляры на соответствие этим законам, поэтому мы должны быть внимательными, чтобы наши экземпляры действительно выполняли их.

 

Познакомьтесь с некоторыми моноидами

 

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

 

Списки являются моноидами

Да, списки являются моноидами! Как вы уже видели, функция ++ с пустым списком [] образуют моноид. Экземпляр очень прост:

instance Monoid [a] where

   mempty = []

   mappend = (++)

Для списков имеется экземпляр класса Monoid независимо от типа элементов, которые они содержат. Обратите внимание, что мы написали instance Monoid [a], а не instance Monoid [], поскольку класс Monoid требует конкретный тип для экземпляра.

При тестировании мы не встречаем сюрпризов:

ghci> [1,2,3] `mappend` [4,5,6]

[1,2,3,4,5,6]

ghci> ("один" `mappend` "два") `mappend` "три"

"одиндватри"

ghci> "один" `mappend` ("два" `mappend` "три")

"одиндватри"

ghci> "один" `mappend` "два" `mappend` "три"

"одиндватри"

ghci> "бах" `mappend` mempty

"бах"

ghci> mconcat [[1,2],[3,6],[9]]

[1,2,3,6,9]

ghci> mempty :: [a]

[]

Обратите внимание, что в последней строке мы написали явную аннотацию типа. Если бы было написано просто mempty, то интерпретатор GHCi не знал бы, какой экземпляр использовать, поэтому мы должны были сказать, что нам нужен списковый экземпляр. Мы могли использовать общий тип [a] (в отличие от указания [Int] или [String]), потому что пустой список может действовать так, будто он содержит любой тип.

Поскольку функция mconcat имеет реализацию по умолчанию, мы получаем её просто так, когда определяем экземпляр класса Monoid для какого-либо типа. В случае со списком функция mconcat соответствует просто функции concat. Она принимает список списков и «разглаживает» его, потому что это равнозначно вызову оператора ++ между всеми смежными списками, содержащимися в списке.

Законы моноидов действительно выполняются для экземпляра списка. Когда у нас есть несколько списков и мы объединяем их с помощью функции mappend (или ++), не имеет значения, какие списки мы соединяем первыми, поскольку так или иначе они соединяются на концах. Кроме того, пустой список действует как единица, поэтому всё хорошо.

Обратите внимание, что моноиды не требуют, чтобы результат выражения a `mappend` b был равен результату выражения b `mappend` a. В случае со списками они очевидно не равны:

ghci> "один" `mappend` "два"

"одиндва"

ghci> "два" `mappend` "один"

"дваодин"

И это нормально. Тот факт, что при умножении выражения 3 * 5 и 5 * 3 дают один и тот же результат, – это просто свойство умножения, но оно не выполняется для большинства моноидов.

 

Типы Product и Sum

Мы уже изучили один из способов рассматривать числа как моноиды: просто позволить бинарной функции быть оператором *, а единичному значению – быть 1. Ещё один способ для чисел быть моноидами состоит в том, чтобы в качестве бинарной функции выступал оператор +, а в качестве единичного значения – значение 0:

ghci> 0 + 4

4

ghci> 5 + 0

5

ghci> (1 + 3) + 5

9

ghci> 1 + (3 + 5)

9

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

Итак, в нашем распоряжении два одинаково правомерных способа для чисел быть моноидами. Какой же способ выбрать?.. Ладно, мы не обязаны выбирать! Вспомните, что когда имеется несколько способов определения для какого-то типа экземпляра одного и того же класса типов, мы можем обернуть этот тип в декларацию newtype, а затем сделать для нового типа экземпляр класса типов по-другому. Можно совместить несовместимое.

Модуль Data.Monoid экспортирует для этого два типа: Product и Sum.

Product определён вот так:

newtype Product a = Product { getProduct :: a }

   deriving (Eq, Ord, Read, Show, Bounded)

Это всего лишь обёртка newtype с одним параметром типа наряду с некоторыми порождёнными экземплярами. Его экземпляр для класса Monoid выглядит примерно так:

instance Num a => Monoid (Product a) where

   mempty = Product 1

   Product x `mappend` Product y = Product (x * y)

Значение mempty – это просто 1, обёрнутая в конструктор Product. Функция mappend производит сопоставление конструктора Product с образцом, перемножает два числа, а затем оборачивает результирующее число. Как вы можете видеть, имеется ограничение класса Num a. Это значит, что Product a является экземпляром Monoid для всех значений типа a, для которых уже имеется экземпляр класса Num. Для того чтобы использовать тип Product a в качестве моноида, мы должны произвести некоторое оборачивание и разворачивание newtype:

ghci> getProduct $ Product 3 `mappend` Product 9

27

ghci> getProduct $ Product 3 `mappend` mempty

3

ghci> getProduct $ Product 3 `mappend` Product 4 `mappend` Product 2

24

ghci> getProduct . mconcat . map Product $ [3,4,2]

24

Тип Sum определён в том же духе, что и тип Product, и экземпляр тоже похож. Мы используем его точно так же:

ghci> getSum $ Sum 2 `mappend` Sum 9

11

ghci> getSum $ mempty `mappend` Sum 3

3

ghci> getSum . mconcat . map Sum $ [1,2,3]

6

 

Типы Any и All

Ещё одним типом, который может действовать как моноид двумя разными, но одинаково допустимыми способами, является Bool. Первый способ состоит в том, чтобы заставить функцию ||, которая представляет собой логическое ИЛИ, действовать как бинарная функция, используя False в качестве единичного значения. Если при использовании логического ИЛИ какой-либо из параметров равен True, функция возвращает True; в противном случае она возвращает False. Поэтому если мы используем False в качестве единичного значения, операция ИЛИ вернёт False при использовании с False – и True при использовании с True. Конструктор newtype Any аналогичным образом имеет экземпляр класса Monoid. Он определён вот так:

newtype Any = Any { getAny :: Bool }

   deriving (Eq, Ord, Read, Show, Bounded)

А его экземпляр выглядит так:

instance Monoid Any where

   mempty = Any False

   Any x `mappend` Any y = Any (x || y)

Он называется Any, потому что x `mappend` y будет равно True, если любое из этих двух значений равно True. Даже когда три или более значений Bool, обёрнутых в Any, объединяются с помощью функции mappend, результат будет содержать True, если любое из них равно True.

ghci> getAny $ Any True `mappend` Any False

True

ghci> getAny $ mempty `mappend` Any True

True

ghci> getAny . mconcat . map Any $ [False, False, False, True]

True

ghci> getAny $ mempty `mappend` mempty

False

Другой возможный вариант экземпляра класса Monoid для типа Bool – всё как бы наоборот: заставить оператор && быть бинарной функцией, а затем сделать значение True единичным значением. Логическое И вернёт True, только если оба его параметра равны True.

Это объявление newtype:

newtype All = All { getAll :: Bool }

   deriving (Eq, Ord, Read, Show, Bounded)

А это экземпляр:

instance Monoid All where

   mempty = All True

   All x `mappend` All y = All (x && y)

Когда мы объединяем значения типа All с помощью функции mappend, результатом будет True только в случае, если все значения, использованные в функции mappend, равны True:

ghci> getAll $ mempty `mappend` All True

True

ghci> getAll $ mempty `mappend` All False

False

ghci> getAll . mconcat . map All $ [True, True, True]

True

ghci> getAll . mconcat . map All $ [True, True, False]

False

Так же, как при использовании умножения и сложения, мы обычно явно указываем бинарные функции вместо оборачивания их в значения newtype и последующего использования функций mappend и mempty. Функция mconcat кажется полезной для типов Any и All, но обычно проще использовать функции or и and. Функция or принимает списки значений типа Bool и возвращает True, если какое-либо из них равно True. Функция and принимает те же значения и возвращает значение True, если все из них равны True.

 

Моноид Ordering

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

ghci> 1 `compare` 2

LT

ghci> 2 `compare` 2

EQ

ghci> 3 `compare` 2

GT

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

instance Monoid Ordering where

   mempty = EQ

   LT `mappend` _ = LT

   EQ `mappend` y = y

   GT `mappend` _ = GT

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

Например, сравнивая слова «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

LT

ghci> GT `mappend` LT

GT

ghci> mempty `mappend` LT

LT

ghci> mempty `mappend` GT

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 "ямб" "хорей"

LT

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

GT

Вспомните, что когда мы используем функцию 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 "ямб" "абыр"

LT

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

LT

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

GT

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

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

 

Моноид Maybe

Рассмотрим несколько способов, которыми для типа Maybe a могут быть определены экземпляры класса Monoid, и обсудим, чем эти экземпляры полезны.

Один из способов состоит в том, чтобы обрабатывать тип Maybe a как моноид, только если его параметр типа a тоже является моноидом, а потом реализовать функцию mappend так, чтобы она использовала операцию mappend для значений, обёрнутых в конструктор Just. Мы используем значение Nothing как единичное, и поэтому если одно из двух значений, которые мы объединяем с помощью функции mappend, равно Nothing, мы оставляем другое значение. Вот объявление экземпляра:

instance Monoid a => Monoid (Maybe a) where

   mempty = Nothing

   Nothing `mappend` m = m

   m `mappend` Nothing = m

   Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)

Обратите внимание на ограничение класса. Оно говорит, что тип Maybe является моноидом, только если для типа a определён экземпляр класса Monoid. Если мы объединяем нечто со значением Nothing, используя функцию mappend, результатом является это нечто. Если мы объединяем два значения Just с помощью функции mappend, то содержимое значений Just объединяется с помощью этой функции, а затем оборачивается обратно в конструктор Just. Мы можем делать это, поскольку ограничение класса гарантирует, что тип значения, которое находится внутри Just, имеет экземпляр класса Monoid.

ghci> Nothing `mappend` Just "андрей"

Just "андрей"

ghci> Just LT `mappend` Nothing

Just LT

ghci> Just (Sum 3) `mappend` Just (Sum 4)

Just (Sum {getSum = 7})

Это полезно, когда мы имеем дело с моноидами как с результатами вычислений, которые могли окончиться неуспешно. Из-за наличия этого экземпляра нам не нужно проверять, окончились ли вычисления неуспешно, определяя, вернули они значение Nothing или Just; мы можем просто продолжить обрабатывать их как обычные моноиды.

Но что если тип содержимого типа Maybe не имеет экземпляра класса Monoid? Обратите внимание: в предыдущем объявлении экземпляра единственный случай, когда мы должны полагаться на то, что содержимые являются моноидами, – это когда оба параметра функции mappend обёрнуты в конструктор Just. Когда мы не знаем, являются ли содержимые моноидами, мы не можем использовать функцию mappend между ними; так что же нам делать? Ну, единственное, что мы можем сделать, – это отвергнуть второе значение и оставить первое. Для этой цели существует тип First a. Вот его определение:

newtype First a = First { getFirst :: Maybe a }

   deriving (Eq, Ord, Read, Show)

Мы берём тип Maybe a и оборачиваем его с помощью декларации newtype. Экземпляр класса Monoid в данном случае выглядит следующим образом:

instance Monoid (Firsta) where

   mempty = First Nothing

   First (Just x) `mappend` _ = First (Just x)

   First Nothing `mappend` x = x

Значение mempty – это просто Nothing, обёрнутое с помощью конструктора First. Если первый параметр функции mappend является значением Just, мы игнорируем второй. Если первый параметр – Nothing, тогда мы возвращаем второй параметр в качестве результата независимо от того, является ли он Just или Nothing:

ghci> getFirst $ First (Just 'a') `mappend` First (Just 'b')

Just 'a'

ghci> getFirst $ First Nothing `mappend` First (Just 'b')

Just 'b'

ghci> getFirst $ First (Just 'a') `mappend` First Nothing

Just 'a'

Тип First полезен, когда у нас есть множество значений типа Maybe и мы хотим знать, является ли какое-либо из них значением Just. Для этого годится функция mconcat:

ghci> getFirst . mconcat . map First $ [Nothing, Just 9, Just 10]

Just 9

Если нам нужен моноид на значениях Maybe a – такой, чтобы оставался второй параметр, когда оба параметра функции mappend являются значениями Just, то модуль Data.Monoid предоставляет тип Last a, который работает, как и тип First a, но при объединении с помощью функции mappend и использовании функции mconcat сохраняется последнее значение, не являющееся Nothing:

ghci> getLast . mconcat . map Last $ [Nothing, Just 9, Just 10]

Just 10

ghci> getLast $ Last (Just "один") `mappend` Last (Just "два")

Just "two"

 

Свёртка на моноидах

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

Поскольку существует так много структур данных, которые хорошо работают со свёртками, был введён класс типов Foldable. Подобно тому как класс Functor предназначен для сущностей, которые можно отображать, класс Foldable предназначен для вещей, которые могут быть свёрнуты! Его можно найти в модуле Data.Foldable; и, поскольку он экспортирует функции, имена которых конфликтуют с именами функций из модуля Prelude, его лучше импортировать, квалифицируя (и подавать с базиликом!):

import qualified Data.Foldable as F

Чтобы сэкономить драгоценные нажатия клавиш, мы импортировали его, квалифицируя как F.

Так какие из некоторых функций определяет этот класс типов? Среди них есть функции foldr, foldl, foldr1 и foldl1. Ну и?.. Мы уже давно знакомы с ними! Что ж в этом нового? Давайте сравним типы функции foldr из модуля Foldable и одноимённой функции из модуля Prelude, чтобы узнать, чем они отличаются:

ghci> :t foldr

foldr :: (a –> b –> b) –> b –> [a] –> b

ghci> :t F.foldr

F.foldr :: (F.Foldable t) => (a –> b –> b) –> b –> t a –> b

А-а-а! Значит, в то время как функция foldr принимает список и сворачивает его, функция foldr из модуля Data.Foldable принимает любой тип, который можно свернуть, – не только списки! Как и ожидалось, обе функции foldr делают со списками одно и то же:

ghci> foldr (*) 1 [1,2,3]

6

ghci> F.foldr (*) 1 [1,2,3]

6

Другой структурой данных, поддерживающей свёртку, является Maybe, которую мы все знаем и любим!

ghci> F.foldl (+) 2 (Just 9)

11

ghci> F.foldr (||) False (Just True)

True

Но сворачивание значения Maybe не очень-то интересно. Оно действует просто как список с одним элементом, если это значение Just, и как пустой список, если это значение Nothing. Давайте рассмотрим чуть более сложную структуру данных.

Помните древовидную структуру данных из главы 7? Мы определили её так:

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

Вы узнали, что дерево – это либо пустое дерево, которое не содержит никаких значений, либо узел, который содержит одно значение, а также два других дерева. После того как мы его определили, мы сделали для него экземпляр класса Functor, и это дало нам возможность отображать его с помощью функций, используя функцию fmap. Теперь мы определим для него экземпляр класса Foldable, чтобы у нас появилась возможность производить его свёртку.

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

foldMap :: (Monoid m, Foldable t) => (a –> m) –> t a –> m

Её первым параметром является функция, принимающая значение того типа, который содержит наша сворачиваемая структура (обозначен здесь как a), и возвращающая моноидное значение. Второй её параметр – сворачиваемая структура, содержащая значения типа a. Эта функция отображает структуру с помощью заданной функции, таким образом, производя сворачиваемую структуру, которая содержит моноидные значения. Затем, объединяя эти моноидные значения с помощью функции mappend, она сводит их все в одно моноидное значение. На данный момент функция может показаться несколько странной, но вы увидите, что её очень просто реализовать. И такой реализации достаточно, чтобы определить для нашего типа экземпляр класса Foldable! Поэтому если мы просто реализуем функцию foldMap для какого-либо типа, то получаем функции foldr и foldl для этого типа даром!

Вот как мы делаем экземпляр класса Foldable для типа:

instance F.Foldable Tree where

   foldMap f EmptyTree = mempty

   foldMap f (Node x l r) = F.foldMap f l `mappend`

                         f x           `mappend`

                         F.foldMap f r

Если нам предоставлена функция, которая принимает элемент нашего дерева и возвращает моноидное значение, то как превратить наше целое дерево в одно моноидное значение? Когда мы использовали функцию fmap с нашим деревом, мы применяли функцию, отображая с её помощью узел, а затем рекурсивно отображали с помощью этой функции левое поддерево, а также правое поддерево. Здесь наша задача состоит не только в отображении с помощью функции, но также и в соединении значений в одно моноидное значение с использованием функции mappend. Сначала мы рассматриваем случай с пустым деревом – печальным и одиноким деревцем, у которого нет никаких значений или поддеревьев. Оно не содержит значений, которые мы можем предоставить нашей функции, создающей моноид, поэтому мы просто говорим, что если наше дерево пусто, то моноидное значение, в которое оно будет превращено, равно значению mempty.

Случай с непустым узлом чуть более интересен. Он содержит два поддерева, а также значение. В этом случае мы рекурсивно отображаем левое и правое поддеревья с помощью одной и той же функции f, используя рекурсивный вызов функции foldMap. Вспомните, что наша функция foldMap возвращает в результате одно моноидное значение. Мы также применяем нашу функцию f к значению в узле. Теперь у нас есть три моноидных значения (два из наших поддеревьев и одно – после применения f к значению в узле), и нам просто нужно соединить их. Для этой цели мы используем функцию mappend, и естественным образом левое поддерево идёт первым, затем – значение узла, а потом – правое поддерево.

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

Теперь, когда у нас есть экземпляр класса Foldable для нашего типа, представляющего дерево, мы получаем функции foldr и foldl даром! Рассмотрите вот это дерево:

testTree = Node 5

            (Node 3

               (Node 1 EmptyTree EmptyTree)

               (Node 6 EmptyTree EmptyTree)

            )

            (Node 9

               (Node 8 EmptyTree EmptyTree)

               (Node 10 EmptyTree EmptyTree)

            )

У него значение 5 в качестве его корня, а его левый узел содержит значение 3 со значениями 1 слева и 6 справа. Правый узел корня содержит значение 9, а затем значения 8 слева от него и 10 в самой дальней части справа. Используя экземпляр класса Foldable, мы можем производить всё те же свёртки, что и над списками:

ghci> F.foldl (+) 0 testTree

42

ghci> F.foldl (*) 1 testTree

64800

Функция foldMap полезна не только для создания новых экземпляров класса Foldable. Она также очень удобна для превращения нашей структуры в одно моноидное значение. Например, если мы хотим узнать, равно ли какое-либо из чисел нашего дерева 3, мы можем сделать следующее:

ghci> getAny $ F.foldMap (\x –> Any $ x == 3) testTree

True

Здесь анонимная функция \x –> Any $ x == 3 – это функция, которая принимает число и возвращает моноидное значение: значение Bool, обёрнутое в тип Any. Функция foldMap применяет эту функцию к каждому элементу нашего дерева, а затем превращает получившиеся моноиды в один моноид с помощью вызова функции mappend. Предположим, мы выполняем следующее:

ghci> getAny $ F.foldMap (\x –> Any $ x > 15) testTree

False

Все узлы нашего дерева будут содержать значение Any False после того, как к ним будет применена анонимная функция. Но чтобы получить в итоге значение True, реализация функции mappend для типа Any должна принять по крайней мере одно значение True в качестве параметра. Поэтому окончательным результатом будет False, что логично, поскольку ни одно значение в нашем дереве не превышает 15.

Мы также можем легко превратить наше дерево в список, просто используя функцию foldMap с анонимной функцией \x –> [x]. Сначала эта функция проецируется на наше дерево; каждый элемент становится одноэлементным списком. Действие функции mappend, которое имеет место между всеми этими одноэлементными списками, возвращает в результате один список, содержащий все элементы нашего дерева:

ghci> F.foldMap (\x –> [x]) testTree

[1,3,6,5,8,9,10]

Самое классное, что все эти трюки не ограничиваются деревьями. Они применимы ко всем экземплярам класса Foldable!