Изучай Haskell во имя добра! (Липовача) - страница 251
>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
Она неэффективна, поскольку производит ассоциацию вызовов оператора >++ влево, вместо того чтобы делать это вправо.
Разностные списки
Поскольку списки иногда могут быть неэффективными при добавлении подобным образом, лучше использовать структуру данных, которая всегда поддерживает эффективное добавление. Одной из таких структур являются