Миран Липовача - Изучай Haskell во имя добра!
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. Балдейте!
Монада 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
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
