gpt4 book ai didi

list - 教会编码列表的更有效的尾部

转载 作者:行者123 更新时间:2023-12-04 01:05:28 26 4
gpt4 key购买 nike

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

最佳答案

论文 Church Encoding of Data Types Considered Harmful for Implementations Koopman、Plasmeijer 和 Jansen 似乎详细地处理了这个问题。特别是引用摘要(我的重点):

[...]

We show that in the Church encoding selectors of constructors yielding the recursive type, like the tail of a list, have an undesirable strictness in the spine of the data structure. The Scott encoding does not hamper lazy evaluation in any way. The evaluation of the recursive spine by the Church encoding makes the complexity of these destructors O(n). The same destructors in the Scott encoding requires only constant time. Moreover, the Church encoding has serious problems with graph reduction. The Parigot encoding combines the best of both worlds, but in practice this does not offer an advantage.



然而,虽然 Scott encoding提供性能优势,它似乎是 problematic在 System F 中定义它而不添加递归类型。

关于list - 教会编码列表的更有效的尾部,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32288370/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com