Неэффективное создание списков

При использовании монады 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

Она неэффективна, поскольку производит ассоциацию вызовов оператора ++ влево, вместо того чтобы делать это вправо.