Некоторые полезные монадические функции

В этом разделе мы изучим несколько функций, которые работа- ют с монадическими значениями либо возвращают монадические значения в качестве своих результатов (или и то, и другое!). Такие функции обычно называют монадическими. В то время как некото- рые из них будут для вас со-

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