Ключевое слово 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

ghci> 1 * 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)

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

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

ghci> 5 + 0

ghci> (1 + 3) + 5

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

в алфавитном порядке. Мы смотрим на первые две буквы, и, если они отличаются, уже можем решить, какое слово шло бы первым в словаре. Если же первые буквы равны, то мы переходим к сравне- нию следующей пары букв, повторяя процесс1.

1 Специалисты по нечёткой логике могут увидеть в этом определении троичную логику Лукасевича. – Прим. ред.

 

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

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

6

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

Maybe, которую мы все знаем и любим!

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

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