更高效的 Church 编码列表尾部

Question

这是一篇关于Haskell的文章。只需将其保存为“ChurchList.lhs”即可运行。

> {-# LANGUAGE Rank2Types #-}

一个 Church 编码列表是一种通过函数表示列表的方式。它类似于折叠和续传风格。

> 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

基本上，我的实现将列表分成头部和尾部。Cons替换头部，并将旧头部添加到尾部。这样做效率相当低下。似乎教堂列表一般在拆分方面效率较低。

我希望我是错误的。是否有比O(n)更好（最好是O(1)）的tailCl实现？

- PyRulez

---

正如Oleg Kiselyov所指出的那样，这实际上是Boehm-Berarducci编码。他在邮件中提供的链接文章非常有趣。 - Petr

Answer 1

论文考虑到实现，数据类型的Church编码是有害的，作者为Koopman、Plasmeijer和Jansen，似乎详细讨论了这个问题。特别是引用摘要（我加粗）：

[...]

我们表明，在Church编码中，构造函数的选择器产生递归类型，例如列表的tail，在数据结构的脊柱上具有不良严格性。Scott编码不会以任何方式阻碍惰性求值。 通过Church编码对递归脊柱的评估使这些析取函数的复杂度为O(n)。相同的析取函数在Scott编码中仅需要常数时间。此外，Church编码在图形减少方面存在严重问题。Parigot编码结合了两种方法的优点，但在实践中并没有提供优势。

然而，虽然Scott编码提供了性能优势，但在不添加递归类型的情况下，在System F中定义它似乎存在问题。

- Petr

---

@PyRulez，Parigot编码允许模式匹配和O(1)的追加操作。这里有一个示例。 - effectfully

@user3237465 Parigot编码并不完全同构，因为其中的Church和Scott部分可能会失去同步。实际上，你链接的代码将创建不一致的Parigot列表。（尝试附加两个列表，然后重复取其尾部。） - PyRulez

@PetrPudlák 我主要是出于理论目的查看教堂列表。不过还是谢谢你。 - PyRulez

@PyRulez，这是我实现中的一个错误——我忘记了pappend中的Scott部分。我已经修复了这个错误，不应该再生成不一致的列表了。干得好。 - effectfully

@user3237465 你会注意到，虽然它可以模拟 Church 列表或 Scott 列表的性能，但无法同时模拟两者。如果同时使用 Church 和 Scott 部分，所有内容都将受到 O(n) 的延迟。除非我错了，但我希望是正确的。 - PyRulez

Answer 2

是的，它是O(n)。一个被编码为 church 表示法的列表通过其 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

- Cirdec

Answer 3

不一定是O(n)：

Prelude> take 5 . snd . foldr (\a r-> (a:fst r,fst r)) ([], undefined) $ [1..] 
[2,3,4,5,6]

它确实为每个元素添加了O(1)的开销，最终产生的每个元素都是如此。

尝试实现safetail没有成功:

Prelude> fmap (take 5) . snd . foldr (\a r-> (fmap (a:) $ fst r,fst r)) (Just [], Nothing) 
   $ [1..] 
  Interrupted.

因此，

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

Prelude> take 5 . toList . tailCL . fromList $ [1..]
[2,3,4,5,6]

结果：[2,3,4,5,6]

---

编辑：根据@user3237465的评论，事实证明safetail是可能的：

Prelude> fmap (take 5) . snd . foldr (\a ~(r,_)-> (Just (a:fromJust r), r)) (Just [] , Nothing) $ [1..]
Just [2,3,4,5,6]

之前它没有起作用的原因是Maybe的fmap强制其第二个参数找出它是哪种情况，但是在这里，我们通过构造知道它是一个Just值。无论我尝试什么，都不能将其作为您类型的定义传递给类型检查器。

- Will Ness

---

然而，当m是一个严格的单子时，对于newtype ChurchList m a = CList { runCList :: forall r. (a -> m r -> m r) -> m r -> m r }这并不起作用。有一种方法可以分割数据结构，但只有外星人才能理解代码。顺便说一句，tail' = snd . foldr (\x ~(r, _)-> (x : r, r)) ([], undefined) 对我来说更具有启示性。 - effectfully

@user3237465，我特意想避免使用懒惰模式，不管出于什么原因。 - Will Ness