Итак, мы зарядили наш пистолет монадой Maybe, списковой монадой и монадой IO. Теперь давайте поместим в патронник монаду Writer и посмотрим, что произойдёт, когда мы выстрелим ею!

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

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

isBigGang :: Int –> Bool

isBigGang x = x > 9

Ну а что если теперь вместо возвращения значения True или False мы хотим, чтобы функция также возвращала строку журнала, которая сообщает, что она сделала? Что ж, мы просто создаём эту строку и возвращаем её наряду с нашим значением Bool:

isBigGang :: Int –> (Bool, String)

isBigGang x = (x > 9, "Размер банды сравнён с 9.")

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

ghci> isBigGang 3

(False,"Размер банды сравнён с 9.")

ghci> isBigGang 30

(True,"Размер банды сравнён с 9.")

Пока всё нормально. Функция isBigGang принимает нормальное значение и возвращает значение с контекстом. Как мы только что увидели, передача ей нормального значения не составляет сложности. Теперь предположим, что у нас уже есть значение, у которого имеется журнальная запись, присоединённая к нему – такая как (3, "Небольшая банда.") – и мы хотим передать его функции isBigGang. Похоже, перед нами снова встаёт вопрос: если у нас есть функция, которая принимает нормальное значение и возвращает значение с контекстом, как нам взять нормальное значение с контекстом и передать его функции?

Исследуя монаду Maybe, мы создали функцию applyMaybe, которая принимала значение типа Maybe a и функцию типа a –> Maybe b и передавала это значение Maybe a в функцию, даже если функция принимает нормальное значение типа a вместо Maybe a. Она делала это, следя за контекстом, имеющимся у значений типа Maybe a, который означает, что эти значения могут быть значениями с неуспехом вычислений. Но внутри функции типа a –> Maybe b мы могли обрабатывать это значение как нормальное, потому что applyMaybe (которая позже стала функцией >>=) проверяла, являлось ли оно значением Nothing либо значением Just.

В том же духе давайте создадим функцию, которая принимает значение с присоединённым журналом, то есть значением типа (a,String), и функцию типа a –> (b,String), и передаёт это значение в функцию. Мы назовём её applyLog. Однако поскольку значение типа (a,String) не несёт с собой контекст возможной неудачи, но несёт контекст добавочного значения журнала, функция applyLog будет обеспечивать сохранность первоначального значения журнала, объединяя его со значением журнала, возвращаемого функцией. Вот реализация этой функции:

applyLog :: (a,String) –> (a –> (b,String)) –> (b,String)

applyLog (x,log) f = let (y,newLog) = f x in (y,log ++ newLog)

Когда у нас есть значение с контекстом и мы хотим передать его функции, то мы обычно пытаемся отделить фактическое значение от контекста, затем пытаемся применить функцию к этому значению, а потом смотрим, сбережён ли контекст. В монаде Maybe мы проверяли, было ли значение равно Just x, и если было, мы брали это значение x и применяли к нему функцию. В данном случае очень просто определить фактическое значение, потому что мы имеем дело с парой, где один компонент является значением, а второй – журналом. Так что сначала мы просто берём значение, то есть x, и применяем к нему функцию f. Мы получаем пару (y,newLog), где y является новым результатом, а newLog – новым журналом. Но если мы вернули это в качестве результата, прежнее значение журнала не было бы включено в результат, так что мы возвращаем пару (y,log ++ newLog). Мы используем операцию конкатенации ++, чтобы добавить новый журнал к прежнему.

Вот функция applyLog в действии:

ghci> (3, "Небольшая банда.") `applyLog` isBigGang

(False,"Небольшая банда.Размер банды сравнён с 9.")

ghci> (30, "Бешеный взвод.") `applyLog` isBigGang

(True,"Бешеный взвод.Размер банды сравнён с 9.")

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

Вот ещё несколько примеров использования applyLog:

ghci> ("Тобин","Вне закона.") `applyLog` (\x –> (length x "Длина."))

(5,"Вне закона.Длина.")

ghci> ("Котопёс","Вне закона.") `applyLog` (\x –> (length x "Длина."))

(7,"Вне закона.Длина.")

Смотрите, как внутри анонимной функции образец x является просто нормальной строкой, а не кортежем, и как функция applyLog заботится о добавлении записей журнала.

Моноиды приходят на помощь

Убедитесь, что вы на данный момент знаете, что такое моноиды!

Прямо сейчас функция applyLog принимает значения типа (a,String), но есть ли смысл в том, чтобы тип журнала был String? Он использует операцию ++ для добавления записей журнала – не будет ли это работать и в отношении любого типа списков, не только списка символов? Конечно же, будет! Мы можем пойти дальше и изменить тип этой функции на следующий:

applyLog :: (a,[c]) –> (a –> (b,[c])) –> (b,[c])

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

Сработало бы это для строк байтов? Нет причины, по которой это не сработало бы! Однако тип, который у нас имеется, работает только со списками. Похоже, что нам пришлось бы создать ещё одну функцию applyLog для строк байтов. Но подождите! И списки, и строки байтов являются моноидами. По существу, те и другие являются экземплярами класса типов Monoid, а это значит, что они реализуют функцию mappend. Как для списков, так и для строк байтов функция mappend производит конкатенацию. Смотрите:

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

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

ghci> B.pack [99,104,105] `mappend` B.pack [104,117,97,104,117,97]

Chunk "chi" (Chunk "huahua" Empty)

Круто! Теперь наша функция applyLog может работать для любого моноида. Мы должны изменить тип, чтобы отразить это, а также реализацию, потому что следует заменить вызов операции ++ вызовом функции mappend:

applyLog :: (Monoid m) => (a,m) –> (a –> (b,m)) –> (b,m)

applyLog (x,log) f = let (y,newLog) = f x

                     in (y,log `mappend` newLog)

Поскольку сопутствующее значение теперь может быть любым моноидным значением, нам больше не нужно думать о кортеже как о значении и журнале, но мы можем думать о нём как о значении с сопутствующим моноидным значением. Например, у нас может быть кортеж, в котором есть имя предмета и цена предмета в виде моноидного значения. Мы просто используем определение типа newtype Sum, чтобы быть уверенными, что цены добавляются, пока мы работаем с предметами. Вот функция, которая добавляет напиток к обеду какого-то ковбоя:

import Data.Monoid

type Food = String

type Price = Sum Int

addDrink :: Food –> (Food,Price)

addDrink "бобы" = ("молоко", Sum 25)

addDrink "вяленое мясо" = ("виски", Sum 99)

addDrink _ = ("пиво", Sum 30)

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

ghci> Sum 3 `mappend` Sum 9

Sum {getSum = 12}

Функция addDrink довольно проста. Если мы едим бобы, она возвращает "молоко" вместе с Sum 25; таким образом, 25 центов завёрнуты в конструктор Sum. Если мы едим вяленое мясо, то пьём виски, а если едим что-то другое – пьём пиво. Обычное применение этой функции к продукту сейчас было бы не слишком интересно, а вот использование функции applyLog для передачи продукта с указанием цены в саму функцию представляет интерес:

ghci> ("бобы", Sum 10) `applyLog` addDrink

("молоко",Sum {getSum = 35})

ghci> ("вяленое мясо", Sum 25) `applyLog` addDrink

("виски",Sum {getSum = 124})

ghci> ("собачатина", Sum 5) `applyLog` addDrink

("пиво",Sum {getSum = 35})

Молоко стоит 25 центов, но если мы заедаем его бобами за 10 центов, это обходится нам в 35 центов. Теперь ясно, почему присоединённое значение не всегда должно быть журналом – оно может быть любым моноидным значением, и то, как эти два значения объединяются, зависит от моноида. Когда мы производили записи в журнал, они присоединялись в конец, но теперь происходит сложение чисел.

Поскольку значение, возвращаемое функцией addDrink, является кортежем типа (Food,Price), мы можем передать этот результат функции addDrink ещё раз, чтобы функция сообщила нам, какой напиток будет подан в сопровождение к блюду и сколько это нам будет стоить. Давайте попробуем:

ghci> ("собачатина", Sum 5) `applyLog` addDrink `applyLog` addDrink

("пиво",Sum {getSum = 65})

Добавление напитка к какой-нибудь там собачатине вернёт пиво и дополнительные 30 центов, то есть ("пиво", Sum 35). А если мы используем функцию applyLog для передачи этого результата функции addDrink, то получим ещё одно пиво, и результатом будет ("пиво", Sum 65).

Тип Writer

Теперь, когда мы увидели, что значение с присоединённым моноидом ведёт себя как монадическое значение, давайте исследуем экземпляр класса Monad для типов таких значений. Модуль Control.Monad.Writer экспортирует тип Writer w a со своим экземпляром класса Monad и некоторые полезные функции для работы со значениями такого типа.

Прежде всего, давайте исследуем сам тип. Для присоединения моноида к значению нам достаточно поместить их в один кортеж. Тип Writer w a является просто обёрткой newtype для кортежа. Его определение несложно:

newtype Writer w a = Writer { runWriter :: (a, w) }

Чтобы кортеж мог быть сделан экземпляром класса Monad и его тип был отделён от обычного кортежа, он обёрнут в newtype. Параметр типа a представляет тип значения, параметр типа w – тип присоединённого значения моноида.

Экземпляр класса Monad для этого типа определён следующим образом:

instance (Monoid w) => Monad (Writer w) where

   return x = Writer (x, mempty)

   (Writer (x,v)) >>= f = let (Writer (y, v')) = f x

                          in Writer (y, v `mappend` v')

Во-первых, давайте рассмотрим операцию >>=. Её реализация по существу аналогична функции applyLog, только теперь, поскольку наш кортеж обёрнут в тип newtype Writer, мы должны развернуть его перед сопоставлением с образцом. Мы берём значение x и применяем к нему функцию f. Это даёт нам новое значение Writer w a, и мы используем выражение let для сопоставления его с образцом. Представляем y в качестве нового результата и используем функцию mappend для объединения старого моноидного значения с новым. Упаковываем его вместе с результирующим значением в кортеж, а затем оборачиваем с помощью конструктора Writer, чтобы нашим результатом было значение Writer, а не просто необёрнутый кортеж.

Ладно, а что у нас с функцией return? Она должна принимать значение и помещать его в минимальный контекст, который по-прежнему возвращает это значение в качестве результата. Так каким был бы контекст для значений типа Writer? Если мы хотим, чтобы сопутствующее моноидное значение оказывало на другие моноидные значения наименьшее влияние, имеет смысл использовать функцию mempty. Функция mempty используется для представления «единичных» моноидных значений, как, например, "", Sum 0 и пустые строки байтов. Когда мы выполняем вызов функции mappend между значением mempty и каким-либо другим моноидным значением, результатом будет это второе моноидное значение. Так что если мы используем функцию return для создания значения монады Writer, а затем применяем оператор >>= для передачи этого значения функции, окончательным моноидным значением будет только то, что возвращает функция. Давайте используем функцию return с числом 3 несколько раз, только каждый раз будем соединять его попарно с другим моноидом:

ghci> runWriter (return 3 :: Writer String Int)

(3,"")

ghci> runWriter (return 3 :: Writer (Sum Int) Int)

(3,Sum {getSum = 0})

ghci> runWriter (return 3 :: Writer (Product Int) Int)

(3,Product {getProduct = 1})

Поскольку у типа Writer нет экземпляра класса Show, нам пришлось использовать функцию runWriter для преобразования наших значений типа Writer в нормальные кортежи, которые могут быть показаны в виде строки. Для строк единичным значением является пустая строка. Для типа Sum это значение 0, потому что если мы прибавляем к чему-то 0, это что-то не изменяется. Для типа Product единичным значением является 1.

В экземпляре класса Monad для типа Writer не имеется реализация для функции fail; значит, если сопоставление с образцом в нотации do оканчивается неудачно, вызывается функция error.

Использование нотации do с типом Writer

Теперь, когда у нас есть экземпляр класса Monad, мы свободно можем использовать нотацию do для значений типа Writer. Это удобно, когда у нас есть несколько значений типа Writer и мы хотим с ними что-либо делать. Как и в случае с другими монадами, можно обрабатывать их как нормальные значения, и контекст сохраняется для нас. В этом случае все моноидные значения, которые идут в присоединённом виде, объединяются с помощью функции mappend, а потому отражаются в окончательном результате. Вот простой пример использования нотации do с типом Writer для умножения двух чисел:

import Control.Monad.Writer

logNumber :: Int –> Writer [String] Int

logNumber x = Writer (x, ["Получено число: " ++ show x])

multWithLog :: Writer [String] Int

multWithLog = do

   a <– logNumber 3

   b <– logNumber 5

   return (a*b)

Функция logNumber принимает число и создаёт из него значение типа Writer. Для моноида мы используем список строк и снабжаем число одноэлементным списком, который просто говорит, что мы получили это число. Функция multWithLog – это значение типа Writer, которое перемножает 3 и 5 и гарантирует включение прикреплённых к ним журналов в окончательный журнал. Мы используем функцию return, чтобы вернуть значение (a*b) в качестве результата. Поскольку функция return просто берёт что-то и помещает в минимальный контекст, мы можем быть уверены, что она ничего не добавит в журнал. Вот что мы увидим, если выполним этот код:

ghci> runWriter multWithLog

(15,["Получено число: 3","Получено число: 5"])

Добавление в программы функции журналирования

Иногда мы просто хотим, чтобы некое моноидное значение было включено в каком-то определённом месте. Для этого может пригодиться функция tell. Она является частью класса типов MonadWriter и в случае с типом Writer берёт монадическое значение вроде ["Всё продолжается"] и создаёт значение типа Writer, которое возвращает значение-пустышку () в качестве своего результата, но прикрепляет желаемое моноидное значение. Когда у нас есть монадическое значение, которое в качестве результата содержит значение (), мы не привязываем его к переменной. Вот определение функции multWithLog с включением некоторых дополнительных сообщений:

multWithLog :: Writer [String] Int

multWithLog = do

   a <– logNumber 3

   b <– logNumber 5

   tell ["Перемножим эту парочку"]

   return (a*b)

Важно, что вызов return (a*b) находится в последней строке, потому что результат последней строки в выражении do является результатом всего выражения do. Если бы мы поместили вызов функции tell на последнюю строку, результатом этого выражения do было бы (). Мы бы потеряли результат умножения. Однако журнал остался бы прежним. Вот функция в действии:

ghci> runWriter multWithLog

(15,["Получено число: 3","Получено число: 5","Перемножим эту парочку"])

Добавление журналирования в программы

Алгоритм Евклида – это алгоритм, который берёт два числа и вычисляет их наибольший общий делитель, то есть самое большое число, на которое делятся без остатка оба числа. В языке Haskell уже имеется функция gcd, которая проделывает это, но давайте реализуем её сами, а затем снабдим её возможностями журналирования. Вот обычный алгоритм:

gcd' :: Int –> Int –> Int

gcd' a b

   | b == 0 = a

   | otherwise = gcd' b (a `mod` b)

Алгоритм очень прост. Сначала он проверяет, равно ли второе число 0. Если равно, то результатом становится первое число. Если не равно, то результатом становится наибольший общий делитель второго числа и остаток от деления первого числа на второе. Например, если мы хотим узнать, каков наибольший общий делитель 8 и 3, мы просто следуем изложенному алгоритму. Поскольку 3 не равно 0, мы должны найти наибольший общий делитель 3 и 2 (если мы разделим 8 на 3, остатком будет 2). Затем ищем наибольший общий делитель 3 и 2. Число 2 по-прежнему не равно 0, поэтому теперь у нас есть 2 и 1. Второе число не равно 0, и мы выполняем алгоритм ещё раз для 1 и 0, поскольку деление 2 на 1 даёт нам остаток равный 0. И наконец, поскольку второе число равно 0, финальным результатом становится 1. Давайте посмотрим, согласуется ли наш код:

ghci> gcd' 8 3

1

Согласуется. Очень хорошо! Теперь мы хотим снабдить наш результат контекстом, а контекстом будет моноидное значение, которое ведёт себя как журнал. Как и прежде, мы используем список строк в качестве моноида. Поэтому тип нашей новой функции gcd' должен быть таким:

gcd' :: Int –> Int –> Writer [String] Int

Всё, что осталось сделать, – снабдить нашу функцию журнальными значениями. Вот код:

import Control.Monad.Writer

gcd' :: Int –> Int –> Writer [String] Int

gcd' a b

   | b == 0 = do

      tell ["Закончили: " ++ show a]

      return a

   | otherwise = do

      tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]

      gcd' b (a `mod` b)

Эта функция принимает два обычных значения Int и возвращает значение типа Writer [String] Int, то есть целое число, обладающее контекстом журнала. В случае, когда параметр b принимает значение 0, мы, вместо того чтобы просто вернуть значение a как результат, используем выражение do для сборки значения Writer в качестве результата. Сначала используем функцию tell, чтобы сообщить об окончании, а затем – функцию return для возврата значения a в качестве результата выражения do. Вместо данного выражения do мы также могли бы написать следующее:

Writer (a, ["Закончили: " ++ show a])

Однако я полагаю, что выражение do проще читать. Далее, у нас есть случай, когда значение b не равно 0. В этом случае мы записываем в журнал, что используем функцию mod для определения остатка от деления a и b. Затем вторая строка выражения do просто рекурсивно вызывает gcd'. Вспомните: функция gcd' теперь, в конце концов, возвращает значение типа Writer, поэтому вполне допустимо наличие строки gcd' b (a `mod` b) в выражении do.

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

Давайте испытаем нашу новую функцию gcd'. Её результатом является значение типа Writer [String] Int, и если мы развернём его из принадлежащего ему newtype, то получим кортеж. Первая часть кортежа – это результат. Посмотрим, правильный ли он:

ghci> fst $ runWriter (gcd 8 3)

1

Хорошо! Теперь что насчёт журнала? Поскольку журнал является списком строк, давайте используем вызов mapM_ putStrLn для вывода этих строк на экран:

ghci> mapM_ putStrLn $ snd $ runWriter (gcd 8 3)

8 mod 3 = 2

3 mod 2 = 1

2 mod 1 = 0

Закончили: 1

Даже удивительно, как мы могли изменить наш обычный алгоритм на тот, который сообщает, что он делает по мере развития, просто превращая обычные значения в монадические и возлагая беспокойство о записях в журнал на реализацию оператора >>= для типа Writer!.. Мы можем добавить механизм журналирования почти в любую функцию. Всего лишь заменяем обычные значения значениями типа Writer, где мы хотим, и превращаем обычное применение функции в вызов оператора >>= (или выражения do, если это повышает «читабельность»).

Неэффективное создание списков

При использовании монады Writer вы должны внимательно выбирать моноид, поскольку использование списков иногда очень замедляет работу программы. Причина в том, что списки задействуют оператор конкатенации ++ в качестве реализации метода mappend, а использование данного оператора для присоединения чего-либо в конец списка заставляет программу существенно медлить, если список длинный.

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

a ++ (b ++ (c ++ (d ++ (e ++ f))))

Списки – это структура данных, построение которой происходит слева направо, и это эффективно, поскольку мы сначала полностью строим левую часть списка и только потом добавляем более длинный список справа. Но если мы невнимательны, то использование монады Writer может вызывать присоединение списков, которое выглядит следующим образом:

((((a ++ b) ++ c) ++ d) ++ e) ++ f

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

Следующая функция работает аналогично функции gcd', но производит журналирование в обратном порядке. Сначала она создаёт журнал для остальной части процедуры, а затем добавляет текущий шаг к концу журнала.

import Control.Monad.Writer

gcdReverse :: Int –> Int –> Writer [String] Int

gcdReverse a b

   | b == 0 = do

      tell ["Закончили: " ++ show a]

      return a

   | otherwise = do

      result <– gcdReverse b (a `mod` b)

      tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]

      return result

Сначала она производит рекурсивный вызов и привязывает его значение к значению result. Затем добавляет текущий шаг в журнал, но текущий попадает в конец журнала, который был произведён посредством рекурсивного вызова. В заключение функция возвращает результат рекурсии как окончательный. Вот она в действии:

ghci> mapM_ putStrLn $ snd $ runWriter (gcdReverse 8 3)

Закончили: 1

2 mod 1 = 0

3 mod 2 = 1

8 mod 3 = 2

Она неэффективна, поскольку производит ассоциацию вызовов оператора ++ влево, вместо того чтобы делать это вправо.

Разностные списки

Поскольку списки иногда могут быть неэффективными при добавлении подобным образом, лучше использовать структуру данных, которая всегда поддерживает эффективное добавление. Одной из таких структур являются разностные списки. Разностный список аналогичен обычному списку, только он является функцией, которая принимает список и присоединяет к нему другой список спереди. Разностным списком, эквивалентным списку [1,2,3], была бы функция \xs –> [1,2,3] ++ xs. Обычным пустым списком является значение [], тогда как пустым разностным списком является функция \xs –> [] ++ xs.

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

f `append` g = \xs –> f (g xs)

Вспомните: f и g – это функции, которые принимают списки и добавляют что-либо в их начало. Так, например, если f – это функция ("соба"++) – просто другой способ записи \xs –> "dog" ++ xs, а g – это функция ("чатина"++), то f `append` g создаёт новую функцию, которая аналогична следующей записи:

\xs –> "соба" ++ ("чатина" ++ xs)

Мы соединили два разностных списка, просто создав новую функцию, которая сначала применяет один разностный список к какому-то одному списку, а затем к другому.

Давайте создадим обёртку newtype для разностных списков, чтобы мы легко могли сделать для них экземпляры класса Monoid:

newtype DiffList a = DiffList { getDiffList :: [a] –> [a] }

Оборачиваемым нами типом является тип [a] –> [a], поскольку разностный список – это просто функция, которая принимает список и возвращает другой список. Преобразовывать обычные списки в разностные и обратно просто:

toDiffList :: [a] –> DiffList a

toDiffList xs = DiffList (xs++)

fromDiffList :: DiffList a –> [a]

fromDiffList (DiffList f) = f []

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

Вот экземпляр класса Monoid:

instance Monoid (DiffList a) where

   mempty = DiffList (\xs –> [] ++ xs)

   (DiffList f) `mappend` (DiffList g) = DiffList (\xs –> f (g xs))

Обратите внимание, что для разностных списков метод mempty – это просто функция id, а метод mappend на самом деле – всего лишь композиция функций. Посмотрим, сработает ли это:

ghci> fromDiffList (toDiffList [1,2,3,4] `mappend` toDiffList [1,2,3])

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

Превосходно! Теперь мы можем повысить эффективность нашей функции gcdReverse, сделав так, чтобы она использовала разностные списки вместо обычных:

import Control.Monad.Writer

gcdReverse :: Int –> Int –> Writer (DiffList String) Int

gcdReverse a b

   | b == 0 = do

      tell (toDiffList ["Закончили: " ++ show a])

      return a

   | otherwise = do

      result <– gcdReverse b (a `mod` b)

      tell (toDiffList [show a ++ " mod " ++ show b ++ " = "

                        ++ show (a `mod` b)])

      return result

Нам всего лишь нужно было изменить тип моноида с [String] на DiffList String, а затем при использовании функции tell преобразовать обычные списки в разностные с помощью функции toDiffList. Давайте посмотрим, правильно ли соберётся журнал:

ghci> mapM_ putStrLn . fromDiffList . snd . runWriter $ gcdReverse 110 34

Закончили: 2

8 mod 2 = 0

34 mod 8 = 2

110 mod 34 = 8

Мы выполняем вызов выражения gcdReverse 110 34, затем используем функцию runWriter, чтобы развернуть его результат из newtype, потом применяем к нему функцию snd, чтобы просто получить журнал, далее – функцию fromDiffList, чтобы преобразовать его в обычный список, и в заключение выводим его записи на экран.

Сравнение производительности

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

finalCountDown :: Int –> Writer (DiffList String) ()

finalCountDown 0 = tell (toDiffList ["0"])

finalCountDown x = do

   finalCountDown (x-1)

   tell (toDiffList [show x])

Если мы передаём ей значение 0, она просто записывает это значение в журнал. Для любого другого числа она сначала вычисляет предшествующее ему число в обратном направлении до 0, а затем добавляет это число в конец журнала. Поэтому если мы применим функцию finalCountDown к значению 100, строка "100" будет идти в журнале последней.

Если вы загрузите эту функцию в интерпретатор GHCi и примените её к большому числу, например к значению 500 000, то увидите, что она быстро начинает счёт от 0 и далее:

ghci> mapM_ putStrLn . fromDiffList .snd . runWriter $ finalCountDown 500000

0

1

2

...

Однако если вы измените её, чтобы она использовала обычные списки вместо разностных, например, так:

finalCountDown :: Int –> Writer [String] ()

finalCountDown 0 = tell ["0"]

finalCountDown x = do

   finalCountDown (x-1)

   tell [show x]

а затем скажете интерпретатору GHCi, чтобы он начал отсчёт:

ghci> mapM_ putStrLn . snd . runWriter $ finalCountDown 500000

вы увидите, что вычисления идут очень медленно.

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

Ну, теперь в вашей голове наверняка засела песня «Final Countdown» группы Europe. Балдейте!

В главе 11 вы видели, что тип функции (–>) r является экземпляром класса Functor. Отображение функции g с помощью функции f создаёт функцию, которая принимает то же, что и g, применяет к этому g, а затем применяет к результату f. В общем, мы создаём новую функцию, которая похожа на g, только перед возвращением своего результата также применяет к этому результату f. Вот пример:

ghci> let f = (*5)

ghci> let g = (+3)

ghci> (fmap f g) 8

55

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

ghci> let f = (+) <$> (*2) <*> (+10)

ghci> f 3

19

Выражение (+) <$> (*2) <*> (+10) создаёт функцию, которая принимает число, передаёт это число функциям (*2) и (+10), а затем складывает результаты. К примеру, если мы применим эту функцию к 3, она применит к 3 и (*2), и (+10), возвращая 6 и 13. Затем она вызовет операцию (+) со значениями 6 и 13, и результатом станет 19.

Функции в качестве монад

Тип функции (–>) r является не только функтором и аппликативным функтором, но также и монадой. Как и другие монадические значения, которые вы встречали до сих пор, функцию можно рассматривать как значение с контекстом. Контекстом для функции является то, что это значение ещё не представлено и нам необходимо применить эту функцию к чему-либо, чтобы получить её результат.

Поскольку вы уже знакомы с тем, как функции работают в качестве функторов и аппликативных функторов, давайте прямо сейчас взглянем, как выглядит их экземпляр для класса Monad. Он расположен в модуле Control.Monad.Instances и похож на нечто подобное:

instance Monad ((–>) r) where

   return x = \_ –> x

   h >>= f = \w –> f (h w) w

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

Реализация для операции >>= может выглядеть немного загадочно, но на самом деле она не так уж и сложна. Когда мы используем операцию >>= для передачи монадического значения функции, результатом всегда будет монадическое значение. Так что в данном случае, когда мы передаём функцию другой функции, результатом тоже будет функция. Вот почему результат начинается с анонимной функции.

Все реализации операции >>= до сих пор так или иначе отделяли результат от монадического значения, а затем применяли к этому результату функцию f. То же самое происходит и здесь. Чтобы получить результат из функции, нам необходимо применить её к чему-либо, поэтому мы используем здесь (h w), а затем применяем к этому f. Функция f возвращает монадическое значение, которое в нашем случае является функцией, поэтому мы применяем её также и к значению w.

Монада Reader

Если в данный момент вы не понимаете, как работает операция >>=, не беспокойтесь. Несколько примеров позволят вам убедиться, что это очень простая монада. Вот выражение do, которое её использует:

import Control.Monad.Instances

addStuff :: Int –> Int

addStuff = do

   a <– (*2)

   b <– (+10)

   return (a+b)

Это то же самое, что и аппликативное выражение, которое мы записали ранее, только теперь оно полагается на то, что функции являются монадами. Выражение do всегда возвращает монадическое значение, и данное выражение ничем от него не отличается. Результатом этого монадического значения является функция. Она принимает число, затем к этому числу применяется функция (*2) и результат записывается в образец a. К тому же самому числу, к которому применялась функция (*2), применяется теперь уже функция (+10), и результат записывается в образец b. Функция return, как и в других монадах, не имеет никакого другого эффекта, кроме создания монадического значения, возвращающего некий результат. Она возвращает значение выражения (a+b) в качестве результата данной функции. Если мы протестируем её, то получим те же результаты, что и прежде:

ghci> addStuff 3

19

И функция (*2), и функция (+10) применяются в данном случае к числу 3. Выражение return (a+b) применяется тоже, но оно игнорирует это значение и всегда возвращает (a+b) в качестве результата. По этой причине функциональную монаду также называют монадой-читателем. Все функции читают из общего источника. Чтобы сделать это ещё очевиднее, мы можем переписать функцию addStuff вот так:

addStuff :: Int –> Int

addStuff x = let a = (*2) x

                 b = (+10) x

             in a+b

Вы видите, что монада-читатель позволяет нам обрабатывать функции как значения с контекстом. Мы можем действовать так, как будто уже знаем, что вернут функции. Суть в том, что монада-читатель «склеивает» функции в одну, а затем передаёт параметр этой функции всем тем, которые её составляют. Поэтому если у нас есть множество функций, каждой из которых недостаёт всего лишь одного параметра, и в конечном счёте они будут применены к одному и тому же, то мы можем использовать монаду-читатель, чтобы как бы извлечь их будущие результаты. А реализация операции >>= позаботится о том, чтобы всё это сработало.

Haskell является чистым языком, и вследствие этого наши программы состоят из функций, которые не могут изменять какое бы то ни было глобальное состояние или переменные – они могут только производить какие-либо вычисления и возвращать результаты. На самом деле данное ограничение упрощает задачу обдумывания наших программ, освобождая нас от необходимости заботиться о том, какое значение имеет каждая переменная в определённый момент времени.

Тем не менее некоторые задачи по своей природе обладают состоянием, поскольку зависят от какого-то состояния, изменяющегося с течением времени. Хотя это не проблема для Haskell, такие вычисления могут быть немного утомительными для моделирования. Вот почему в языке Haskell есть монада State, благодаря которой решение задач с внутренним состоянием становится сущим пустяком – и в то же время остаётся красивым и чистым.

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

threeCoins :: StdGen –> (Bool, Bool, Bool)

threeCoins gen =

   let (firstCoin, newGen) = random gen

       (secondCoin, newGen') = random newGen

       (thirdCoin, newGen'') = random newGen'

   in (firstCoin, secondCoin, thirdCoin)

Эта функция принимает генератор gen, а затем вызов random gen возвращает значение типа Bool наряду с новым генератором. Для подбрасывания второй монеты мы используем новый генератор, и т. д.

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

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

Вычисления с состоянием

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

s –> (a, s)

Идентификатор s обозначает тип состояния; a – это результат вычислений с состоянием.

ПРИМЕЧАНИЕ. В большинстве других языков присваивание значения может рассматриваться как вычисление с состоянием. Например, когда мы выполняем выражение x = 5 в императивном языке, как правило, это присваивает переменной x значение 5 , и в нём также в качестве выражения будет фигурировать значение 5 . Если рассмотреть это действие с функциональной точки зрения, получается нечто вроде функции, принимающей состояние (то есть все переменные, которым ранее были присвоены значения) и возвращающей результат (в данном случае 5 ) и новое состояние, которое представляло бы собой все предшествующие соответствия переменных значениям плюс переменную с недавно присвоенным значением.

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

Стеки и чебуреки

Предположим, мы хотим смоделировать стек. Стек – это структура данных, которая содержит набор элементов и поддерживает ровно две операции:

• проталкивание элемента в стек (добавляет элемент на верхушку стека);

• выталкивание элемента из стека (удаляет самый верхний элемент из стека).

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

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

• функция push будет принимать элемент и стек, а затем проталкивать этот элемент в стек. В качестве результата она будет возвращать значение () вместе с новым стеком.

Вот используемые функции:

type Stack = [Int]

pop :: Stack –> (Int, Stack)

pop (x:xs) = (x, xs)

push :: Int –> Stack –> ((), Stack)

push a xs = ((), a:xs)

При проталкивании в стек в качестве результата мы использовали значение (), поскольку проталкивание элемента на вершину стека не несёт какого-либо существенного результирующего значения – его основная задача заключается в изменении стека. Если мы применим только первый параметр функции push, мы получим вычисление с состоянием. Функция pop уже является вычислением с состоянием вследствие своего типа.

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

stackManip :: Stack –> (Int, Stack)

stackManip stack = let

   ((), newStack1) = push 3 stack

   (a , newStack2) = pop newStack1

   in pop newStack2

Мы принимаем стек, а затем выполняем выражение push 3 stack, что даёт в результате кортеж. Первой частью кортежа является значение (), а второй частью является новый стек, который мы называем newStack1. Затем мы выталкиваем число из newStack1, что даёт в результате число a (равно 3), которое мы протолкнули, и новый стек, названный нами newStack2. Затем мы выталкиваем число из newStack2 и получаем число и новый стек. Мы возвращаем кортеж с этим числом и новым стеком. Давайте попробуем:

ghci> stackManip [5,8,2,1]

(5,[8,2,1])

Результат равен 5, а новый стек – [8,2,1]. Обратите внимание, как функция stackManip сама является вычислением с состоянием. Мы взяли несколько вычислений с состоянием и как бы «склеили» их вместе. Хм-м, звучит знакомо.

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

stackManip = do

   push 3

   a <– pop

   pop

Ла-адно, монада State позволит нам делать именно это!.. С её помощью мы сможем брать вычисления с состоянием, подобные этим, и использовать их без необходимости управлять состоянием вручную.

Монада State

Модуль Control.Monad.State предоставляет тип newtype, который оборачивает вычисления с состоянием. Вот его определение:

newtype State s a = State { runState :: s –> (a, s) }

Тип State s a – это тип вычисления с состоянием, которое манипулирует состоянием типа s и имеет результат типа a.

Как и модуль Control.Monad.Writer, модуль Control.Monad.State не экспортирует свой конструктор значения. Если вы хотите взять вычисление с состоянием и обернуть его в newtype State, используйте функцию state, которая делает то же самое, что делал бы конструктор State.

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

instance Monad (State s) where

   return x = State $ \s –> (x, s)

   (State h) >>= f = State $ \s –> let (a, newState) = h s

                                       (State g) = f a

                                   in g newState

Наша цель использования функции return состоит в том, чтобы взять значение и создать вычисление с состоянием, которое всегда содержит это значение в качестве своего результата. Поэтому мы просто создаём анонимную функцию \s –> (x, s). Мы всегда представляем значение x в качестве результата вычисления с состоянием, а состояние остаётся неизменным, так как функция return должна помещать значение в минимальный контекст. Потому функция return создаст вычисление с состоянием, которое представляет определённое значение в качестве результата, а состояние сохраняет неизменным.

А что насчёт операции >>=? Ну что ж, результатом передачи вычисления с состоянием функции с помощью операции >>= должно быть вычисление с состоянием, верно? Поэтому мы начинаем с обёртки newtype State, а затем вызываем анонимную функцию. Эта анонимная функция будет нашим новым вычислением с состоянием. Но что же в ней происходит? Нам каким-то образом нужно извлечь значение результата из первого вычисления с состоянием. Поскольку прямо сейчас мы находимся в вычислении с состоянием, то можем передать вычислению с состоянием h наше текущее состояние s, что в результате даёт пару из результата и нового состояния: (a, newState).

До сих пор каждый раз, когда мы реализовывали операцию >>=, сразу же после извлечения результата из монадического значения мы применяли к нему функцию f, чтобы получить новое монадическое значение. В случае с монадой Writer после того, как это сделано и получено новое монадическое значение, нам по-прежнему нужно позаботиться о контексте, объединив прежнее и новое моноидные значения с помощью функции mappend. Здесь мы выполняем вызов выражения f a и получаем новое вычисление с состоянием g. Теперь, когда у нас есть новое вычисление с состоянием и новое состояние (известное под именем newState), мы просто применяем это вычисление с состоянием g к newState. Результатом является кортеж из окончательного результата и окончательного состояния!

Итак, при использовании операции >>= мы как бы «склеиваем» друг с другом два вычисления, обладающих состоянием. Второе вычисление скрыто внутри функции, которая принимает результат предыдущего вычисления. Поскольку функции pop и push уже являются вычислениями с состоянием, легко обернуть их в обёртку State:

import Control.Monad.State

pop :: State Stack Int

pop = state $ \(x:xs) –> (x, xs)

push :: Int –> State Stack ()

push a = state $ \xs –> ((), a:xs)

Обратите внимание, как мы задействовали функцию state, чтобы обернуть функцию в конструктор newtype State, не прибегая к использованию конструктора значения State напрямую.

Функция pop – уже вычисление с состоянием, а функция push принимает значение типа Int и возвращает вычисление с состоянием. Теперь мы можем переписать наш предыдущий пример проталкивания числа 3 в стек и выталкивания двух чисел подобным образом:

import Control.Monad.State

stackManip :: State Stack Int

stackManip = do

   push 3

   a <– pop

   pop

Видите, как мы «склеили» проталкивание и два выталкивания в одно вычисление с состоянием? Разворачивая его из обёртки newtype, мы получаем функцию, которой можем предоставить некое исходное состояние:

ghci> runState stackManip [5,8,2,1]

(5,[8,2,1])

Нам не требовалось привязывать второй вызов функции pop к образцу a, потому что мы вовсе не использовали этот образец. Значит, это можно было записать вот так:

stackManip :: State Stack Int

stackManip = do

   push 3

   pop

   pop

Очень круто! Но что если мы хотим сделать что-нибудь посложнее? Скажем, вытолкнуть из стека одно число, и если это число равно 5, просто протолкнуть его обратно в стек и остановиться. Но если число не равно 5, вместо этого протолкнуть обратно 3 и 8. Вот он код:

stackStuff :: State Stack ()

stackStuff = do

   a <– pop

   if a == 5

      then push 5

      else do

         push 3

         push 8

Довольно простое решение. Давайте выполним этот код с исходным стеком:

ghci> runState stackStuff [9,0,2,1,0] ((),[8,3,0,2,1,0])

Вспомните, что выражения do возвращают в результате монадические значения, и при использовании монады State одно выражение do является также функцией с состоянием. Поскольку функции stackManip и stackStuff являются обычными вычислениями с состоянием, мы можем «склеивать» их вместе, чтобы производить дальнейшие вычисления с состоянием:

moreStack :: State Stack ()

moreStack = do

   a <– stackManip

   if a == 100

      then stackStuff

      else return ()

Если результат функции stackManip при использовании текущего стека равен 100, мы вызываем функцию stackStuff; в противном случае ничего не делаем. Вызов return () просто сохраняет состояние как есть и ничего не делает.

Получение и установка состояния

Модуль Control.Monad.State определяет класс типов под названием MonadState, в котором присутствуют две весьма полезные функции: get и put. Для монады State функция get реализована вот так:

get = state $ \s –> (s, s)

Она просто берёт текущее состояние и представляет его в качестве результата.

Функция put принимает некоторое состояние и создаёт функцию с состоянием, которая заменяет им текущее состояние:

put newState = state $ \s –> ((), newState)

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

stackyStack :: State Stack ()

stackyStack = do

   stackNow <– get

   if stackNow == [1,2,3]

      then put [8,3,1]

      else put [9,2,1]

Также можно использовать функции get и put, чтобы реализовать функции pop и push. Вот определение функции pop:

pop :: State Stack Int

pop = do

   (x:xs) <– get

   put xs

   return x

Мы используем функцию get, чтобы получить весь стек, а затем – функцию put, чтобы новым состоянием были все элементы за исключением верхнего. После чего прибегаем к функции return, чтобы представить значение x в качестве результата.

Вот определение функции push, реализованной с использованием get и put:

push :: Int –> State Stack ()

push x = do

   xs <– get

   put (x:xs)

Мы просто используем функцию get, чтобы получить текущее состояние, и функцию put, чтобы установить состояние в такое же, как наш стек с элементом x на вершине.

Стоит проверить, каким был бы тип операции >>=, если бы она работала только со значениями монады State:

(>>=) :: State s a –> (a –> State s b) –> State s b

Видите, как тип состояния s остаётся тем же, но тип результата может изменяться с a на b? Это означает, что мы можем «склеивать» вместе несколько вычислений с состоянием, результаты которых имеют различные типы, но тип состояния должен оставаться тем же. Почему же так?.. Ну, например, для типа Maybe операция >>= имеет такой тип:

(>>=) :: Maybe a –> (a –> Maybe b) –> Maybe b

Логично, что сама монада Maybe не изменяется. Не имело бы смысла использовать операцию >>= между двумя разными монадами. Для монады State монадой на самом деле является State s, так что если бы этот тип s был различным, мы использовали бы операцию >>= между двумя разными монадами.

Случайность и монада State

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

Функция random из модуля System.Random имеет следующий тип:

random :: (RandomGen g, Random a) => g –> (a, g)

Это значит, что она берёт генератор случайных чисел и производит случайное число вместе с новым генератором. Нам видно, что это вычисление с состоянием, поэтому мы можем обернуть его в конструктор newtype State при помощи функции state, а затем использовать его в качестве монадического значения, чтобы передача состояния обрабатывалась за нас:

import System.Random

import Control.Monad.State

randomSt :: (RandomGen g, Random a) => State g a

randomSt = state random

Поэтому теперь, если мы хотим подбросить три монеты (True – это «решка», а False – «орёл»), то просто делаем следующее:

import System.Random

import Control.Monad.State

threeCoins :: State StdGen (Bool, Bool, Bool)

threeCoins = do

   a <– randomSt

   b <– randomSt

   c <– randomSt

   return (a, b, c)

Функция threeCoins – это теперь вычисление с состоянием, и после получения исходного генератора случайных чисел она передаёт этот генератор в первый вызов функции randomSt, которая производит число и новый генератор, передаваемый следующей функции, и т. д. Мы используем выражение return (a, b, c), чтобы представить значение (a, b, c) как результат, не изменяя самый последний генератор. Давайте попробуем:

ghci> runState threeCoins (mkStdGen 33)

((True,False,True),680029187 2103410263)

Теперь выполнение всего, что требует сохранения некоторого состояния в промежутках между шагами, в самом деле стало доставлять значительно меньше хлопот!

В этом разделе мы изучим несколько функций, которые работают с монадическими значениями либо возвращают монадические значения в качестве своих результатов (или и то, и другое!). Такие функции обычно называют монадическими. В то время как некоторые из них будут для вас совершенно новыми, другие являются монадическими аналогами функций, с которыми вы уже знакомы – например, filter и foldl. Ниже мы рассмотрим функции liftM, join, filterM и foldM.

liftM и компания

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

Итак, каждая монада – это аппликативный функтор, а каждый аппликативный функтор – это функтор. Класс типов Applicative имеет такое ограничение класса, ввиду которого наш тип должен иметь экземпляр класса Functor, прежде чем мы сможем сделать для него экземпляр класса Applicative. Класс Monad должен иметь то же самое ограничение для класса Applicative, поскольку каждая монада является аппликативным функтором – однако не имеет, потому что класс типов Monad был введён в язык Haskell задолго до класса Applicative.

Но хотя каждая монада – функтор, нам не нужно полагаться на то, что у неё есть экземпляр для класса Functor, в силу наличия функции liftM. Функция liftM берёт функцию и монадическое значение и отображает монадическое значение с помощью функции. Это почти одно и то же, что и функция fmap! Вот тип функции liftM:

liftM :: (Monad m) => (a –> b) –> m a –> m b

Сравните с типом функции fmap:

fmap :: (Functor f) => (a –> b) –> f a –> f b

Если экземпляры классов Functor и Monad для типа подчиняются законам функторов и монад, между этими двумя нет никакой разницы (и все монады, которые мы до сих пор встречали, подчиняются обоим). Это примерно как функции pure и return, делающие одно и то же, – только одна имеет ограничение класса Applicative, тогда как другая имеет ограничение Monad.

Давайте опробуем функцию liftM:

ghci> liftM (*3) (Just 8)

Just 24

ghci> fmap (*3) (Just 8)

Just 24

ghci> runWriter $ liftM not $ Writer (True, "горох")

(False,"горох")

ghci> runWriter $ fmap not $ Writer (True, "горох")

(False,"горох")

ghci> runState (liftM (+100) pop) [1,2,3,4]

(101,[2,3,4])

ghci> runState (fmap (+100) pop) [1,2,3,4]

(101,[2,3,4])

Вы уже довольно хорошо знаете, как функция fmap работает со значениями типа Maybe. И функция liftM делает то же самое. При использовании со значениями типа Writer функция отображает первый компонент кортежа, который является результатом. Выполнение функций fmap или liftM с вычислением, имеющим состояние, даёт в результате другое вычисление с состоянием, но его окончательный результат изменяется добавленной функцией. Если бы мы не отобразили функцию pop с помощью (+100) перед тем, как выполнить её, она бы вернула (1, [2,3,4]).

Вот как реализована функция liftM:

liftM :: (Monad m) => (a –> b) –> m a –> m b

liftM f m = m >>= (\x –> return (f x))

Или с использованием нотации do:

liftM :: (Monad m) => (a –> b) –> m a –> m b

liftM f m = do

   x <– m

   return (f x)

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

Вы видите, что функция liftM реализована совсем не ссылаясь на класс типов Functor. Значит, мы можем реализовать функцию fmap (или liftM – называйте, как пожелаете), используя лишь те блага, которые предоставляют нам монады. Благодаря этому можно заключить, что монады, по крайней мере, настолько же сильны, насколько и функторы.

Класс типов Applicative позволяет нам применять функции между значениями с контекстами, как если бы они были обычными значениями, вот так:

ghci> (+) <$> Just 3 <*> Just 5

Just 8

ghci> (+) <$> Just 3 <*> Nothing

Nothing

Использование этого аппликативного стиля всё упрощает. Операция <$> – это просто функция fmap, а операция <*> – это функция из класса типов Applicative, которая имеет следующий тип:

(<*>) :: (Applicative f) => f (a –> b) –> f a –> f b

Так что это вроде fmap, только сама функция находится в контексте. Нам нужно каким-то образом извлечь её из контекста и с её помощью отобразить значение f a, а затем вновь собрать контекст. Поскольку все функции в языке Haskell по умолчанию каррированы, мы можем использовать сочетание из операций <$> и <*> между аппликативными значениями, чтобы применять функции, принимающие несколько параметров.

Однако, оказывается, как и функция fmap, операция <*> тоже может быть реализована, используя лишь то, что даёт нам класс типов Monad. Функция ap, по существу, – это <*>, только с ограничением Monad, а не Applicative. Вот её определение:

ap :: (Monad m) => m (a –> b) –> m a –> m b

ap mf m = do

   f <– mf

   x <– m

   return (fx)

Функция ap – монадическое значение, результат которого – функция. Поскольку функция, как и значение, находится в контексте, мы берём функцию из контекста и называем её f, затем берём значение и называем его x, и, в конце концов, применяем функцию к значению и представляем это в качестве результата. Вот быстрая демонстрация:

ghci> Just (+3) <*> Just 4

Just 7

ghci> Just (+3) `ap` Just 4

Just 7

ghci> [(+1),(+2),(+3)] <*> [10,11]

[11,12,12,13,13,14]

ghci> [(+1),(+2),(+3)] `ap` [10,11]

[11,12,12,13,13,14]

Теперь нам видно, что монады настолько же сильны, насколько и аппликативные функторы, потому что мы можем использовать методы класса Monad для реализации функций из класса Applicative. На самом деле, когда обнаруживается, что определённый тип является монадой, зачастую сначала записывают экземпляр класса Monad, а затем создают экземпляр класса Applicative, просто говоря, что функция pure – это return, а операция <*> – это ap. Аналогичным образом, если у вас уже есть экземпляр класса Monad для чего-либо, вы можете сделать для него экземпляр класса Functor, просто говоря, что функция fmap – это liftM.

Функция liftA2 весьма удобна для применения функции между двумя аппликативными значениями. Она определена вот так:

liftA2 :: (Applicative f) => (a –> b –> c) –> f a –> f b –> f c

liftA2 f x y = f <$> x <*> y

Функция liftM2 делает то же, но с использованием ограничения Monad. Есть также функции liftM3, liftM4 и liftM5.

Вы увидели, что монады не менее сильны, чем функторы и аппликативные функторы – и, хотя все монады, по сути, являются функторами и аппликативными функторами, у них необязательно имеются экземпляры классов Functor и Applicative. Мы изучили монадические эквиваленты функций, которые используются функторами и аппликативными функторами.

Функция join

Есть кое-какая пища для размышления: если результат монадического значения – ещё одно монадическое значение (одно монадическое значение вложено в другое), можете ли вы «разгладить» их до одного лишь обычного монадического значения? Например, если у нас есть Just (Just 9), можем ли мы превратить это в Just 9? Оказывается, что любое вложенное монадическое значение может быть разглажено, причём на самом деле это свойство уникально для монад. Для этого у нас есть функция join. Её тип таков:

join :: (Monad m) => m (m a) –> m a

Значит, функция join принимает монадическое значение в монадическом значении и отдаёт нам просто монадическое значение; другими словами, она его разглаживает. Вот она с некоторыми значениями типа Maybe:

ghci> join (Just (Just 9))

Just 9

ghci> join (Just Nothing)

Nothing

ghci> join Nothing

Nothing

В первой строке – успешное вычисление как результат успешного вычисления, поэтому они оба просто соединены в одно большое успешное вычисление. Во второй строке значение Nothing представлено как результат значения Just. Всякий раз, когда мы раньше имели дело со значениями Maybe и хотели объединить несколько этих значений – будь то с использованием операций <*> или >>= – все они должны были быть значениями конструктора Just, чтобы результатом стало значение Just. Если на пути возникала хоть одна неудача, то и результатом являлась неудача; нечто аналогичное происходит и здесь. В третьей строке мы пытаемся разгладить то, что возникло вследствие неудачи, поэтому результат – также неудача.

Разглаживание списков осуществляется довольно интуитивно:

ghci> join [[1,2,3],[4,5,6]]

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

Как вы можете видеть, функция join для списков – это просто concat. Чтобы разгладить значение монады Writer, результат которого сам является значением монады Writer, нам нужно объединить моноидное значение с помощью функции mappend:

ghci> runWriter $ join (Writer (Writer (1, "aaa"), "bbb"))

(1,"bbbaaa")

Внешнее моноидное значение "bbb" идёт первым, затем к нему конкатенируется строка "aaa". На интуитивном уровне, когда вы хотите проверить результат значения типа Writer, сначала вам нужно записать его моноидное значение в журнал, и только потом вы можете посмотреть, что находится внутри него.

Разглаживание значений монады Either очень похоже на разглаживание значений монады Maybe:

ghci> join (Right (Right 9)) :: Either String Int

Right 9

ghci> join (Right (Left "ошибка")) :: Either String Int

Left "ошибка"

ghci> join (Left "ошибка") :: Either String Int

Left "ошибка"

Если применить функцию join к вычислению с состоянием, результат которого является вычислением с состоянием, то результатом будет вычисление с состоянием, которое сначала выполняет внешнее вычисление с состоянием, а затем результирующее. Взгляните, как это работает:

ghci> runState (join (state $ \s –> (push 10, 1:2:s))) [0,0,0]

((),[10,1,2,0,0,0])

Здесь анонимная функция принимает состояние, помещает 2 и 1 в стек и представляет push 10 как свой результат. Поэтому когда всё это разглаживается с помощью функции join, а затем выполняется, всё это выражение сначала помещает значения 2 и 1 в стек, а затем выполняется выражение push 10, проталкивая число 10 на верхушку.

Реализация для функции join такова:

join :: (Monad m) => m (m a) –> m a

join mm = do

   m <– mm

   m

Поскольку результат mm является монадическим значением, мы берём этот результат, а затем просто помещаем его на его собственную строку, потому что это и есть монадическое значение. Трюк здесь в том, что когда мы вызываем выражение m <– mm, контекст монады, в которой мы находимся, будет обработан. Вот почему, например, значения типа Maybe дают в результате значения Just, только если и внешнее, и внутреннее значения являются значениями Just. Вот как это выглядело бы, если бы значение mm было заранее установлено в Just (Just 8):

joinedMaybes :: Maybe Int

joinedMaybes = do

   m <– Just (Just 8)

   m

Наверное, самое интересное в функции join – то, что для любой монады передача монадического значения в функцию с помощью операции >>= представляет собой то же самое, что и просто отображение значения с помощью этой функции, а затем использование функции join для разглаживания результирующего вложенного монадического значения! Другими словами, выражение m >>= f – всегда то же самое, что и join (fmap f m). Если вдуматься, это имеет смысл.

При использовании операции >>= мы постоянно думаем, как передать монадическое значение функции, которая принимает обычное значение, а возвращает монадическое. Если мы просто отобразим монадическое значение с помощью этой функции, то получим монадическое значение внутри монадического значения. Например, скажем, у нас есть Just 9 и функция \x –> Just (x+1). Если с помощью этой функции мы отобразим Just 9, у нас останется Just (Just 10).

То, что выражение m >>= f всегда равно join (fmap f m), очень полезно, если мы создаём свой собственный экземпляр класса Monad для некоего типа. Это связано с тем, что зачастую проще понять, как мы бы разгладили вложенное монадическое значение, чем понять, как реализовать операцию >>=.

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

Функция filterM

Функция filter – это просто хлеб программирования на языке Haskell (при том что функция map – масло). Она принимает предикат и список, подлежащий фильтрации, а затем возвращает новый список, в котором сохраняются только те элементы, которые удовлетворяют предикату. Её тип таков:

filter :: (a –> Bool) –> [a] –> [a]

Предикат берёт элемент списка и возвращает значение типа Bool. А вдруг возвращённое им значение типа Bool было на самом деле монадическим? Что если к нему был приложен контекст?.. Например, каждое значение True или False, произведённое предикатом, имело также сопутствующее моноидное значение вроде ["Принято число 5"] или ["3 слишком мало"]? Если бы это было так, мы бы ожидали, что к результирующему списку тоже прилагается журнал всех журнальных значений, которые были произведены на пути. Поэтому если бы к списку, возвращённому предикатом, возвращающим значение типа Bool, был приложен контекст, мы ожидали бы, что к результирующему списку тоже прикреплён некоторый контекст. Иначе контекст, приложенный к каждому значению типа Bool, был бы утрачен.

Функция filterM из модуля Control.Monad делает именно то, что мы хотим! Её тип таков:

filterM :: (Monad m) => (a –> m Bool) –> [a] –> m [a]

Предикат возвращает монадическое значение, результат которого – типа Bool, но поскольку это монадическое значение, его контекст может быть всем чем угодно, от возможной неудачи до недетерминированности и более! Чтобы обеспечить отражение контекста в окончательном результате, результат тоже является монадическим значением.

Давайте возьмём список и оставим только те значения, которые меньше 4. Для начала мы используем обычную функцию filter:

ghci> filter (\x –> x < 4) [9,1,5,2,10,3]

[1,2,3]

Это довольно просто. Теперь давайте создадим предикат, который помимо представления результата True или False также предоставляет журнал своих действий. Конечно же, для этого мы будем использовать монаду Writer:

keepSmall :: Int –> Writer [String] Bool

keepSmall x

   | x < 4 = do

        tell ["Сохраняем " ++ show x]

        return True

   | otherwise = do

        tell [show x ++ " слишком велико, выбрасываем"]

        return False

Вместо того чтобы просто возвращать значение типа Bool, функция возвращает значение типа Writer [String] Bool. Это монадический предикат. Звучит необычно, не так ли? Если число меньше числа 4, мы сообщаем, что оставили его, а затем возвращаем значение True.

Теперь давайте передадим его функции filterM вместе со списком. Поскольку предикат возвращает значение типа Writer, результирующий список также будет значением типа Writer.

ghci> fst $ runWriter $ filterM keepSmall [9,1,5,2,10,3]

[1,2,3]

Проверяя результат результирующего значения монады Writer, мы видим, что всё в порядке. Теперь давайте распечатаем журнал и посмотрим, что у нас есть:

ghci> mapM_ putStrLn $ snd $ runWriter $ filterM keepSmall [9,1,5,2,10,3]

9 слишком велико, выбрасываем

Сохраняем 1

5 слишком велико, выбрасываем

Сохраняем 2

10 слишком велико, выбрасываем

Сохраняем 3

Итак, просто предоставляя монадический предикат функции filterM, мы смогли фильтровать список, используя возможности применяемого нами монадического контекста.

Очень крутой трюк в языке Haskell – использование функции filterM для получения множества-степени списка (если мы сейчас будем думать о нём как о множестве). Множеством – степенью некоторого множества называется множество всех подмножеств данного множества. Поэтому если у нас есть множество вроде [1,2,3], его множество-степень включает следующие множества:

[1,2,3]

[1,2]

[1,3]

[1]

[2,3]

[2]

[3]

[]

Другими словами, получение множества-степени похоже на получение всех сочетаний сохранения и выбрасывания элементов из множества. Например, [2,3] – это исходное множество с исключением числа 1; [1,2] – это исходное множество с исключением числа 3 и т. д.

Чтобы создать функцию, которая возвращает множество-степень какого-то списка, мы положимся на недетерминированность. Мы берём список [1,2,3], а затем смотрим на первый элемент, который равен 1, и спрашиваем себя: «Должны ли мы его сохранить или отбросить?» Ну, на самом деле мы хотели бы сделать и то и другое. Поэтому мы отфильтруем список и используем предикат, который сохраняет и отбрасывает каждый элемент из списка недетерминированно. Вот наша функция powerset:

powerset :: [a] –> [[a]]

powerset xs = filterM (\x –> [True, False]) xs

Стоп, это всё?! Угу! Мы решаем отбросить и оставить каждый элемент независимо от того, что он собой представляет. У нас есть недетерминированный предикат, поэтому результирующий список тоже будет недетерминированным значением – и потому будет списком списков. Давайте попробуем:

ghci> powerset [1,2,3]

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

Вам потребуется немного поразмыслить, чтобы понять это. Просто воспринимайте списки как недетерминированные значения, которые толком не знают, чем быть, поэтому решают быть сразу всем, – и эту концепцию станет проще усвоить!

Функция foldM

Монадическим аналогом функции foldl является функция foldM. Если вы помните свои свёртки из главы 5, вы знаете, что функция foldl принимает бинарную функцию, исходный аккумулятор и сворачиваемый список, а затем сворачивает его слева в одно значение, используя бинарную функцию. Функция foldM делает то же самое, только она принимает бинарную функцию, производящую монадическое значение, и сворачивает список с её использованием. Неудивительно, что результирующее значение тоже является монадическим. Тип функции foldl таков:

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

Тогда как функция foldM имеет такой тип:

foldM :: (Monad m) => (a –> b –> m a) –> a –> [b] –> m a

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

ghci> foldl (\acc x –> acc + x) 0 [2,8,3,1]

14

Исходный аккумулятор равен 0, затем к аккумулятору прибавляется 2, что даёт в результате новый аккумулятор со значением 2. К этому аккумулятору прибавляется 8, что даёт в результате аккумулятор равный 10 и т. д. Когда мы доходим до конца, результатом является окончательный аккумулятор.

А ну как мы захотели бы сложить список чисел, но с дополнительным условием: если какое-то число в списке больше 9, всё должно окончиться неудачей? Имело бы смысл использовать бинарную функцию, которая проверяет, больше ли текущее число, чем 9. Если больше, то функция оканчивается неудачей; если не больше – продолжает свой радостный путь. Из-за этой добавленной возможности неудачи давайте заставим нашу бинарную функцию возвращать аккумулятор Maybe вместо обычного.

Вот бинарная функция:

binSmalls :: Int –> Int –> Maybe Int

binSmalls acc x

   | x > 9     = Nothing

   | otherwise = Just (acc + x)

Поскольку наша бинарная функция теперь является монадической, мы не можем использовать её с обычной функцией foldl; следует использовать функцию foldM. Приступим:

ghci> foldM binSmalls 0 [2,8,3,1]

Just 14

ghci> foldM binSmalls 0 [2,11,3,1]

Nothing

Клёво! Поскольку одно число в списке было больше 9, всё дало в результате значение Nothing. Свёртка с использованием бинарной функции, которая возвращает значение Writer, – тоже круто, потому что в таком случае вы журналируете что захотите по ходу работы вашей свёртки.