12

这是一个有文化的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 替换了头部，并将旧的头部附加到尾部。这是相当低效的。似乎教会列表在拆分方面通常效率低下。

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

4

3 回答 3

6

Koopman、Plasmeijer 和 Jansen 对被认为对实现有害的数据类型的纸上教堂编码似乎详细处理了这个问题。特别是引用摘要（我的重点）：

[...]

我们表明，在产生递归类型的构造函数的 Church 编码选择器中，就像列表的尾部一样，在数据结构的脊椎中具有不良的严格性。Scott 编码不会以任何方式妨碍惰性求值。Church 编码对递归脊柱的评估使得这些析构函数的复杂度为O(n)。Scott 编码中的相同析构函数只需要恒定时间。此外，Church 编码在图形缩减方面存在严重问题。Parigot 编码结合了两全其美，但在实践中这并没有提供优势。

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

于 2015-08-29T19:31:15.787 回答
3

是的，它是 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
于 2015-08-29T18:53:32.800 回答
1

不，不一定是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。列表。尾CL 。来自列表 $ [1..]
[2,3,4,5,6]

编辑：在@user3237465的评论之后，事实证明这 safetail毕竟是可能的：

前奏> fmap（取5）。snd foldr (\a ~(r,_)-> (Just (a:fromJust r), r)) (Just [] , Nothing) $ [1..]
Just [2,3,4,5,6]

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

于 2015-08-30T06:47:16.347 回答