为什么差异列表不是可折叠类型的实例？

Question

dlist包 包含了 DList 数据类型，它有很多的实例，但没有 Foldable 或者 Traversable。在我看来，这两个类是最类似“列表”的类。是否有性能原因使得 DList 不是这些类的实例呢？

此外，该包确实实现了 foldr 和 unfoldr 但没有其他的折叠函数。

- Mike Izbicki

Answer 1

除了使用 DList，您应该考虑使用 Church 编码列表。这个想法是将列表表示为一个不透明的值，它知道如何在列表上执行 foldr。这需要使用 RankNTypes 扩展：

{-# LANGUAGE RankNTypes #-}

import Prelude 
import Control.Applicative
import Data.Foldable (Foldable)
import qualified Data.Foldable as F
import Data.Traversable (Traversable)
import qualified Data.Traversable as T

-- | Laws:
--
-- > runList xs cons nil == xs
-- > runList (fromList xs) f z == foldr f z xs
-- > foldr f z (toList xs) == runList xs f z
newtype ChurchList a = 
    ChurchList { runList :: forall r. (a -> r -> r) -> r -> r }

-- | Make a 'ChurchList' out of a regular list.
fromList :: [a] -> ChurchList a
fromList xs = ChurchList $ \k z -> foldr k z xs

-- | Turn a 'ChurchList' into a regular list.
toList :: ChurchList a -> [a]
toList xs = runList xs (:) []

-- | We can construct an empty 'ChurchList' without using a @[]@.
nil :: ChurchList a 
nil = ChurchList $ \_ z -> z

-- | The 'ChurchList' counterpart to '(:)'.  Unlike 'DList', whose
-- implementation uses the regular list type, 'ChurchList' doesn't
-- rely on it at all.
cons :: a -> ChurchList a -> ChurchList a
cons x xs = ChurchList $ \k z -> k x (runList xs k z)

-- | Append two 'ChurchList's.  This runs in O(1) time.  Note that
-- there is no need to materialize the lists as @[a]@.
append :: ChurchList a -> ChurchList a -> ChurchList a
append xs ys = ChurchList $ \k z -> runList xs k (runList ys k z)

-- | Map over a 'ChurchList'.  No need to materialize the list.
instance Functor ChurchList where
    fmap f xs = ChurchList $ \k z -> runList xs (\x xs' -> k (f x) xs') z

-- | The 'Foldable' instance is trivial, given the 'ChurchList' law.
instance Foldable ChurchList where
    foldr f z xs = runList xs f z

instance Traversable ChurchList where
    traverse f xs = runList xs step (pure nil)
        where step x rest = cons <$> f x <*> rest

这样做的缺点是没有有效的tail操作可以用于ChurchList。对ChurchList进行折叠操作很便宜，但是重复地取尾部操作是代价高昂的...

- Luis Casillas

---

一个 ChurchList 的 tail 可以被惰性地在常数时间内计算出来。 - is7s

请注意，我说的是“取重复尾巴”；如果你只取一次尾巴，简单的 churchTail = fromList . tail . toList 看起来并不太糟糕。但现在考虑一下 churchTail . churchTail 会发生什么：你得到一个由 []-list 构造而成的 ChurchList，该列表是由一个由 []-list 支持的 ChurchList 构造而成的。问题的核心是 ChurchList 及其 churchTail 不像 []-list 及其尾部那样共享结构。我认为，即使使用不使用 toList/fromList 的更复杂的 churchTail 实现也无法避免这种情况。 - Luis Casillas

真的，对于其他实现来说，重复的“tails”也是很昂贵的。顺便说一下，我不认为ChurchList的append操作比普通列表好，是吗？ - is7s

@WillNess 它是否已经被打包成一个包，并且带有重写规则？ - Alp Mestanogullari

@AlpMestanogullari 我不知道。 :) - Will Ness

Answer 2

DList a是围绕着[a] -> [a]的newtype包装器, 在这里，a处于反变位置，因此它不能直接实现Foldable或Traversable, 甚至不能直接实现Functor。唯一的实现方式是将其转换为常规列表(请参见foldr实现)，这会破坏差异列表的性能优势。

- Sjoerd Visscher

---

除了Sjoerd的回答之外，DList仅适用于构建 - 如果您已经构建了列表并希望处理它，则应使用toList进行转换，然后处理常规列表。 - stephen tetley

那么为什么我们不简单地定义 fold（DL f）= fold（f []） 呢？我们可以忘记 DList 的实现方式，简单地将其视为元素序列的某种表示形式，然后实现 Foldable 就有意义了。以这种方式实现 Functor 和 Traversable 可能会有一些陷阱，但是以这种方式实现 Foldable 是相当合理的。 - Petr

是的，Foldable 可能还不错，因为该包已经拥有了 foldr，毕竟这已经足够了。我认为它没有被实现的原因是最后一次更新是在2009年，当时 Foldable 还不是很知名的类型类。 - Sjoerd Visscher