Разностные списки

Поскольку списки иногда могут быть неэффективными при добавлении подобным образом, лучше использовать структуру данных, которая всегда поддерживает эффективное добавление. Одной из таких структур являются разностные списки. Разностный список аналогичен обычному списку, только он является функцией, которая принимает список и присоединяет к нему другой список спереди. Разностным списком, эквивалентным списку [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, чтобы преобразовать его в обычный список, и в заключение выводим его записи на экран.