Это грамотный пост на Haskell. Просто сохраните его как "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)).