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

Следующая функция работает аналогично функции 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. Давайте посмотрим, правильно ли соберётся журнал: