>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
вы увидите, что вычисления идут очень медленно.