Более эффективный хвост церковного кодированного списка
Это грамотная почта Хеккеля. Просто сохраните его как "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 по построению. Я бы не сказал, что это определение для вашего типа, но все, что я пробовал, не прошел проверку типа.
