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