Миран Липовача - Изучай Haskell во имя добра!

ghci> gcd' 8 3

1

Согласуется. Очень хорошо! Теперь мы хотим снабдить наш результат контекстом, а контекстом будет моноидное значение, которое ведёт себя как журнал. Как и прежде, мы используем список строк в качестве моноида. Поэтому тип нашей новой функции gcd'должен быть таким:

gcd' :: Int –> Int –> Writer [String] Int

Всё, что осталось сделать, – снабдить нашу функцию журнальными значениями. Вот код:

import Control.Monad.Writer

gcd' :: Int –> Int –> Writer [String] Int

gcd' a b

| b == 0 = do

tell ["Закончили: " ++ show a]

return a

| otherwise = do

tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]

gcd' b (a `mod` b)

Эта функция принимает два обычных значения Intи возвращает значение типа Writer [String] Int, то есть целое число, обладающее контекстом журнала. В случае, когда параметр bпринимает значение 0, мы, вместо того чтобы просто вернуть значение aкак результат, используем выражение doдля сборки значения Writerв качестве результата. Сначала используем функцию tell, чтобы сообщить об окончании, а затем – функцию returnдля возврата значения aв качестве результата выражения do. Вместо данного выражения doмы также могли бы написать следующее:

Writer (a, ["Закончили: " ++ show a])

Однако я полагаю, что выражение doпроще читать. Далее, у нас есть случай, когда значение bне равно 0. В этом случае мы записываем в журнал, что используем функцию modдля определения остатка от деления aи b. Затем вторая строка выражения doпросто рекурсивно вызывает gcd'. Вспомните: функция gcd'теперь, в конце концов, возвращает значение типа Writer, поэтому вполне допустимо наличие строки gcd' b (a `mod` b)в выражении do.

Хотя отслеживание выполнения этой новой функции gcd'вручную может быть отчасти полезным для того, чтобы увидеть, как записи присоединяются в конец журнала, я думаю, что лучше будет взглянуть на картину крупным планом, представляя эти значения как значения с контекстом, и отсюда понять, каким будет окончательный результат.

Давайте испытаем нашу новую функцию gcd'. Её результатом является значение типа Writer [String] Int, и если мы развернём его из принадлежащего ему newtype, то получим кортеж. Первая часть кортежа – это результат. Посмотрим, правильный ли он:

ghci> fst $ runWriter (gcd 8 3)

1

Хорошо! Теперь что насчёт журнала? Поскольку журнал является списком строк, давайте используем вызов mapM_ putStrLnдля вывода этих строк на экран:

ghci> mapM_ putStrLn $ snd $ runWriter (gcd 8 3)

8 mod 3 = 2

3 mod 2 = 1

2 mod 1 = 0

Закончили: 1

Даже удивительно, как мы могли изменить наш обычный алгоритм на тот, который сообщает, что он делает по мере развития, просто превращая обычные значения в монадические и возлагая беспокойство о записях в журнал на реализацию оператора >>=для типа Writer!.. Мы можем добавить механизм журналирования почти в любую функцию. Всего лишь заменяем обычные значения значениями типа Writer, где мы хотим, и превращаем обычное применение функции в вызов оператора >>=(или выражения do, если это повышает «читабельность»).

При использовании монады Writerвы должны внимательно выбирать моноид, поскольку использование списков иногда очень замедляет работу программы. Причина в том, что списки задействуют оператор конкатенации ++в качестве реализации метода mappend, а использование данного оператора для присоединения чего-либо в конец списка заставляет программу существенно медлить, если список длинный.

В нашей функции gcd'журналирование происходит быстро, потому что добавление списка в конец в итоге выглядит следующим образом:

a ++ (b ++ (c ++ (d ++ (e ++ f))))

Списки – это структура данных, построение которой происходит слева направо, и это эффективно, поскольку мы сначала полностью строим левую часть списка и только потом добавляем более длинный список справа. Но если мы невнимательны, то использование монады Writerможет вызывать присоединение списков, которое выглядит следующим образом:

((((a ++ b) ++ c) ++ d) ++ e) ++ f

Здесь связывание происходит в направлении налево, а не направо. Это неэффективно, поскольку каждый раз, когда функция хочет добавить правую часть к левой, она должна построить левую часть полностью, с самого начала!