Голова и хвост по разным спискам в Haskell, à la LYAH

Учите вас, 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?

  • Что еще может спросить, работает ли это в постоянное время, учитывая, что список различий является функцией, а не фактическим "значением"?
  • Выполняется ли headTailDifList в постоянное время?

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

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

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

Ответы

Ответ 1

Изменить: добавлено больше о 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 ++)

Ответ 2

Посмотрите на 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) время для создания всех элементов. Как отметил ДжонЛ, просто создание первого элемента может выполняться в постоянное время.