Более эффективный хвост церковного кодированного списка

Это грамотная почта Хеккеля. Просто сохраните его как "ChurchList.lhs", чтобы запустить его.

> {-# LANGUAGE Rank2Types #-}

Список, закодированный Церковью, представляет собой способ представления списка через функцию. Он похож на стиль сгибания и продолжения прохождения.

> newtype ChurchList a = CList {runCList :: forall r. (a -> r -> r) -> r -> r}

Для иллюстрации того, как это соответствует списку, здесь существует O (n) изоморфизм

> fromList :: [a] -> ChurchList a
> fromList xs = CList $ \cons empty -> foldr cons empty xs

> toList :: ChurchList a -> [a]
> toList cl = runCList cl (:) []

> instance Show a => Show (ChurchList a) where
>   show cl = "fromList " ++ show (toList cl)

Эти вещи обладают хорошими характеристиками производительности.

> singleton :: a -> ChurchList a -- O(1)
> singleton a = CList $ \cons empty -> a `cons` empty
> append :: ChurchList a -> ChurchList a -> ChurchList a -- O(1)!!! This also means cons and snoc are O(1)
> append cl1 cl2 = CList $ \cons empty -> runCList cl1 cons (runCList cl2 cons empty)
> concatCl :: ChurchList (ChurchList a) -> ChurchList a -- O(n)
> concatCl clcl = CList $ \cons empty -> runCList clcl (\cl r -> runCList cl cons r) empty
> headCl :: ChurchList a -> Maybe a -- O(1)
> headCl cl = runCList cl (\a _ -> Just a) Nothing

Теперь проблема связана с tail.

> tailClbad :: ChurchList a -> Maybe (ChurchList a) --O(n)?!!
> tailClbad cl = (fmap snd) $ runCList cl
>
>    (\a r -> Just (a, case r of
>    Nothing -> CList $ \cons empty -> empty
>    Just (s,t) -> append (singleton s) t)) --Cons
>
>    Nothing --Empty

По сути, моя реализация делает разбиение списка на голову и хвост. Минуты заменяют голову и прикладывают старую голову к хвосту. Это довольно неэффективно. Кажется, что Церковные Списки вообще неэффективны при расщеплении.

Я надеюсь, что ошибаюсь. Существует ли реализация tailCl, которая лучше, чем O (n) (предпочтительно O (1)).

Ответ 1

Бумага Кодовое кодирование типов данных, считающихся вредоносными для реализации, Копман, Пласмайер и Янсен, похоже, подробно разбираются в этой проблеме. В частности, цитируя резюме (мой акцент):

[...]

Мы показываем, что в кодировке Церкви селекторы конструкторов приводящий к рекурсивному типу, например, хвост списка, имеют нежелательный строгость в позвоночнике структуры данных. Кодировка Скотта не мешает ленивой оценке каким-либо образом. Оценка рекурсивного позвоночника посредством кодирования в Церкви делает сложность эти деструкторы O (n). Те же деструкторы в кодировке Скотт требуется только постоянное время. Более того, церковная кодировка серьезные проблемы с уменьшением графика. Кодировка Parigot объединяет лучшее из обоих миров, но на практике это не дает преимущество.

Однако, в то время как кодировка Scott обеспечивает преимущество в производительности, представляется проблематичным, чтобы определить ее в Система F без добавления рекурсивных типов.

Ответ 2

Да, это O (n). Список, закодированный в церкви, идентифицируется с его функцией foldr, которая должна делать то же самое везде. Поскольку получение хвоста требует сделать что-то для первого элемента, то же самое нужно сделать для всех остальных элементов.

{-# LANGUAGE RankNTypes #-}

newtype ChurchList a = CList { getFoldr :: forall r. (a -> r -> r) -> r -> r }

fromList :: [a] -> ChurchList a 
fromList xs = CList $ \f z -> foldr f z xs

toList :: ChurchList a -> [a]
toList cl = getFoldr cl ((:)) []

Ваше решение максимально эффективно. Это же решение можно также написать тривиально, построив список и сопоставляя его по первому элементу.

safeTail :: [a] -> Maybe [a]
safeTail []     = Nothing
safeTail (_:xs) = Just xs

tailCtrivial ::  ChurchList a -> Maybe (ChurchList a)
tailCtrivial = fmap fromList . safeTail . toList

Ответ 3

Нет, не обязательно O (n):

Прелюдия > возьмите 5. snd. foldr (\ a r- > (a: fst r, fst r)) ([], undefined) $[1..]
[2,3,4,5,6]

Это действительно добавляет O (1) накладные расходы для каждого элемента в конечном итоге.

Попытка выполнить safetail не помогла:

Прелюдия > fmap (возьмите 5). snd. foldr (\ a r- > (fmap (a:) $fst r, fst r)) (Just [], Nothing)
$ [1..]
Прерванный.

Итак,

tailCL cl = CList $ \k z-> snd $ runCList cl (\a r-> (a`k`fst r,fst r)) (z, undefined)

Прелюдия > возьмите 5. к списку. tailCL. fromList $[1..]
[2,3,4,5,6]

отредактируйте: followng комментарий @user3237465, оказывается, что safetail возможно в конце концов:

Прелюдия > fmap (возьмите 5). snd. foldr (\ a ~ (r, _) → (Just (a: fromJust r), r)) (Just [], Ничего) $[1..]
Просто [2,3,4,5,6]

Причина, по которой она не работала раньше, заключается в том, что Maybe fmap заставляет свой второй аргумент выяснить, в каком именно случае, но здесь мы знаем, что это значение Just по построению. Я бы не сказал, что это определение для вашего типа, но все, что я пробовал, не прошел проверку типа.