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

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

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

Следующая функция работает аналогично функции 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

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

Поскольку списки иногда могут быть неэффективными при добавлении подобным образом, лучше использовать структуру данных, которая всегда поддерживает эффективное добавление. Одной из таких структур являются разностные списки . Разностный список аналогичен обычному списку, только он является функцией, которая принимает список и присоединяет к нему другой список спереди. Разностным списком, эквивалентным списку [1,2,3], была бы функция \xs –> [1,2,3] ++ xs. Обычным пустым списком является значение [], тогда как пустым разностным списком является функция \xs –> [] ++ xs.

Прелесть разностных списков заключается в том, что они поддерживают эффективную конкатенацию. Когда мы «склеиваем» два списка с помощью оператора ++, приходится проходить первый список (левый операнд) до конца и затем добавлять другой.

f `append` g = \xs –> f (g xs)

Вспомните: fи g– это функции, которые принимают списки и добавляют что-либо в их начало. Так, например, если f– это функция ("соба"++)– просто другой способ записи \xs –> "dog" ++ xs, а g– это функция ("чатина"++), то f `append` gсоздаёт новую функцию, которая аналогична следующей записи:

\xs –> "соба" ++ ("чатина" ++ xs)

Мы соединили два разностных списка, просто создав новую функцию, которая сначала применяет один разностный список к какому-то одному списку, а затем к другому.