Добавление журналирования в программы

Алгоритм Евклида – это алгоритм, который берёт два числа и вы- числяет их наибольший общий делитель, то есть самое большое число, на которое делятся без остатка оба числа. В языке Haskell уже имеется функция gcd, которая проделывает это, но давайте ре- ализуем её сами, а затем снабдим её возможностями журналирова- ния. Вот обычный алгоритм:

gcd':: Int –> Int –> Int gcd' a b

| b == 0 = a

| otherwise = gcd' b (a `mod` b)

Алгоритм очень прост. Сначала он проверяет, равно ли второе число 0. Если равно, то результатом становится первое число. Если не равно, то результатом становится наибольший общий делитель второго числа и остаток от деления первого числа на второе. На- пример, если мы хотим узнать, каков наибольший общий делитель 8 и 3, мы просто следуем изложенному алгоритму. Поскольку 3 не рав- но 0, мы должны найти наибольший общий делитель 3 и 2 (если мы разделим 8 на 3, остатком будет 2). Затем ищем наибольший общий делитель 3 и 2. Число 2 по-прежнему не равно 0, поэтому теперь у нас есть 2 и 1. Второе число не равно 0, и мы выполняем алгоритм ещё раз для 1 и 0, поскольку деление 2 на 1 даёт нам остаток равный 0. И наконец, поскольку второе число равно 0, финальным резуль- татом становится 1. Давайте посмотрим, согласуется ли наш код:

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

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

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

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

Давайте создадим обёртку newtype для разностных списков, что- бы мы легко могли сделать для них экземпляры класса Monoid:

newtype DiffList a = DiffList { getDiffList:: [a] –> [a] }

 

Оборачиваемым нами типом является тип [a] –> [a], поскольку разностный список – это просто функция, которая принимает спи- сок и возвращает другой список. Преобразовывать обычные спис- ки в разностные и обратно просто:

toDiffList:: [a] –> DiffList a toDiffList xs = DiffList (xs++)

 

fromDiffList:: DiffList a –> [a] fromDiffList (DiffList f) = f []

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

Вот экземпляр класса Monoid:

instance Monoid (DiffList a) where mempty = DiffList (\xs –> [] ++ xs)

(DiffList f) `mappend` (DiffList g) = DiffList (\xs –> f (g xs))

Обратите внимание, что для разностных списков метод mempty – это просто функция id, а метод mappend на самом деле – всего лишь композиция функций. Посмотрим, сработает ли это:

ghci> fromDiffList (toDiffList [1,2,3,4] `mappend` toDiffList [1,2,3]) [1,2,3,4,1,2,3]

Превосходно! Теперь мы можем повысить эффективность на- шей функции gcdReverse, сделав так, чтобы она использовала раз- ностные списки вместо обычных:

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, чтобы преобразовать его в обыч- ный список, и в заключение выводим его записи на экран.