голова и хвост в списках различий в Haskell, а-ля LYAH - PullRequest
Новая
       26

голова и хвост в списках различий в Haskell, а-ля LYAH

11 голосов
/ 30 ноября 2011

Learn You a Haskell упоминает списки различий (поиск этого термина на этой странице), где список l представлен не напрямую, а в виде функции (l++). Это позволяет более эффективно объединять как слева, так и справа. Конкатенация становится составом функций, и, наконец, можно преобразовать в реальный список ($[]). Мне было интересно, какие операции можно эффективно поддерживать в списках различий. Например, эквивалент (:) для списков различий равен 

\x l -> (x:) . l

Можно ли эффективно реализовать head и tail для списков различий? Вот очевидная реализация: 

headTailDifList :: ([a] -> [a]) -> (a, [a] -> [a])
headTailDifList dl = (head l, ((tail l)++))
    where
    l = dl []

Для реальных списков \l -> (head l, tail l) выполняется в постоянное время. Как насчет этого headTailDifList? Возможно, из-за ленивых вычислений будет оцениваться только первый элемент l?

  1. Что вообще значит спрашивать, выполняется ли это в постоянном времени, учитывая, что список различий является функцией, а не фактическим «значением»?
  2. headTailDifList работает в постоянное время?

  3. Есть ли какая-то другая реализация с постоянным временем? Вот кандидатура: 

    headTailDifList dl = (head (dl []), tail.dl )

    Однако, хвостовая часть не выдает исключение, если dl равно id (пустой список различий).

Ответы [ 2 ]

9 голосов
/ 30 ноября 2011

Редактировать: добавлено больше о Thunk.

Начните с просмотра только преобразования из списка различий в обычный список. Эта операция сама по себе занимает только постоянное время, потому что оценка не требуется. Результирующий список будет существовать как thunk, который будет структурирован примерно так:

enter image description here

Базовое определение (++) является ассоциативным справа и должно пройти через весь первый аргумент, прежде чем он сможет продолжить со вторым аргументом. Это отлично согласуется с вложенной структурой, созданной списком различий, поскольку каждый (++) получает один блок списка в качестве первого аргумента. Кроме того, поскольку (++) является хорошим производителем списков, вся структура существует лениво. Хотя для полной оценки требуется O (n), оценка только головы - это O (k), где k=number of chunks.

Рассмотрим, если a,b == []; c = [1..]. Затем head необходимо сначала проверить, что a и b пусты, прежде чем перейти к c и найти первый элемент. В худшем случае head обойдет всю структуру, прежде чем найдет пустой конструктор списка. Однако на практике это очень редкий случай, и даже в этом случае он не особенно вреден, поскольку обнаружение пустого куска и переход к нему - операция с постоянным временем.

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

Создание только первого элемента списка разностей не требует времени O (n), что легко можно продемонстрировать с помощью бесконечных списков: 

*Dl Control.Monad Control.Applicative> head $ ($ []) $ toDl [1..] . toDl [4..]
1
(0.01 secs, 2110104 bytes)

*Dl Control.Monad Control.Applicative> fmap (head . ($ [])) $ headTailDifList (toDl [1..])
(1,2)
(0.00 secs, 2111064 bytes)

*Dl Control.Monad Control.Applicative> fmap (head . ($ [])) $ headTailDifList (toDl [1..] . toDl [3..] . toDl [] . toDl [5..])
(1,2)
(0.01 secs, 3105792 bytes)

-- create a difference list
toDl :: [a] -> ([a] -> [a])
toDl l = (l ++)
3 голосов
/ 30 ноября 2011

Посмотрите на пакет dlist , который предоставляет типичную реализацию списков различий. Он определяет тип DList: 

newtype DList a = DL { unDL :: [a] -> [a] }

и все общие функции списка, включая head и tail: 

head :: DList a -> a
head = list (error "Data.DList.head: empty list") const

tail :: DList a -> DList a
tail = list (error "Data.DList.tail: empty list") (flip const)

Здесь list определяется как: 

list :: b -> (a -> DList a -> b) -> DList a -> b
list nill consit dl =
  case toList dl of
    [] -> nill
    (x : xs) -> consit x (fromList xs)

с: 

fromList    :: [a] -> DList a
fromList    = DL . (++)

toList      :: DList a -> [a]
toList      = ($[]) . unDL

То есть list требуется O (n) времени, чтобы произвести все элементы. Однако, как отметил ДжонЛ, просто создание первого элемента может выполняться за постоянное время.

...