更高效的教堂编码列表尾部

Question

这是一个有文化的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)).

Answer 1

对于实施有害的数据类型的纸质教会编码考夫曼,Plasmeijer和Jansen似乎详细地解决了这个问题.特别是引用摘要(我的重点):

[...]

我们表明,在Church中编码生成递归类型的构造函数的选择器,如列表的尾部,在数据结构的主干中具有不合需要的严格性.Scott编码不会以任何方式阻碍惰性评估.通过Church编码对递归书脊的评估使得这些析构函数O(n)的复杂性成为可能.Scott编码中的相同析构函数只需要恒定的时间.此外,教会编码在图形缩减方面存在严重问题.Parigot编码结合了两者的优点,但在实践中,这并没有提供优势.

但是,虽然Scott编码提供了性能优势,但在System F中定义它并不添加递归类型似乎存在问题.

Answer 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