Миран Липовача - Изучай 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