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

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

МОНАДА Reader? ТЬФУ, ОПЯТЬ ЭТИ ШУТОЧКИ! 425

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

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

...

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

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 Count- down» группы Europe. Балдейте!

 

Монада Reader?

Тьфу, опять эти шуточки!

В главе 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

МОНАДА Reader? ТЬФУ, ОПЯТЬ ЭТИ ШУТОЧКИ 427

 

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

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