5

在Haskell 中，差异列表

[a] 具有高效连接操作的列表表示

似乎是在功能组合方面实现的。

但是，函数和（动态）函数组合也必须以某种方式在计算机内存中使用数据结构来表示，这引发了一个问题，即如何在 Haskell 中实现dlist而不使用函数组合，而是通过一些基本的纯函数基于节点的数据结构。如何在与函数组合相同的性能保证下做到这一点？

4

3 回答 3

3

卡尔在他的评论中击中了它。我们可以写

data TList a = Nil | Single a | Node !(TList a) (TList a)

singleton :: a -> TList a
singleton = Single

instance Monoid (TList a) where
  mempty = Nil
  mappend = Node

我们可以toList通过推导得到Foldable，但是让我们把它写出来看看到底发生了什么。

instance Foldable TList where
  foldMap _ Nil = mempty
  foldMap f (Single a) = f a
  foldMap f (Node t u) = foldMap f t <> foldMap f u

  toList as0 = go as0 [] where
    go Nil k = k
    go (Single a) k = a : k
    go (Node l r) k = go l (go r k)

toList是 O(n)，其中 n 是内部节点的总数（即，mappend用于形成 的操作的总数TList）。这应该很清楚：每个Node都只检查一次。mempty, mappend, 和singleton每个显然都是 O(1)。

这与 a 完全相同DList：

newtype DList a = DList ([a] -> [a])
singletonD :: a -> DList a
singletonD a = DList (a:)
instance Monoid (DList a) where
  mempty = DList id
  mappend (DList f) (DList g) = DList (f . g)
instance Foldable DList where
  foldr c n xs = foldr c n (toList xs)
  toList (DList f) = f []

为什么在操作上是一样的？因为，正如您在问题中指出的那样，函数在内存中表示为树。它们被表示为看起来很像TLists 的树！singletonD x产生一个包含一个（无聊）(:)和一个令人兴奋的闭包x。应用时，它确实 O(1) 工作。mempty只产生id函数，应用时 O(1) 工作。mappend as bs产生一个闭包，当应用它时，它自己做 O(1) 工作，加上 O(length as + length bs) 在它的孩子身上工作。

为和实际生产的树木的形状是相同的。您应该能够说服自己，在增量使用时它们也具有相同的渐近性能：在每种情况下，程序都必须沿着树的左脊向下移动才能到达第一个列表元素。TListDList

两者都一样DList，TList在建立然后只使用一次时同样可以。它们在构建一次并多次转换为列表时同样糟糕。

正如 Will Ness 用类似的类型展示的那样，如果您想添加对解构表示的支持，那么显式树表示会更好，因为您实际上可以掌握结构。TList可以支持合理有效的uncons操作（在工作时改进结构）。为了提高效率unsnoc，您需要使用更高级的表示形式（可连接的双端队列）。此实现还具有潜在的糟糕缓存性能。您可以切换到缓存忽略数据结构，但实际上可以保证它很复杂。

于 2017-05-12T19:46:20.140 回答
3

如this answer所示，诀窍是将(.)树重新排列到($)访问列表中。

我们可以用

data Dlist a = List [a]  
             | Append (Dlist a) (Dlist a)

这将调整Append节点，向右旋转树，将最左边的节点向上推，使其成为最左上角，在第一次访问时，下一个tail(**)操作变为O(1)  <sup>( *) :

let x = (List [1..10] `Append` List [11..20]) `Append` List [21..30]

和tail x(**)是生产

List [2..10] `Append` (List [11..20] `Append` List [21..30])

tail(**)应该很容易实现。当然，当最终发现该节点时， if 只会与最左侧List节点的列表（带有(x:xs)）进行模式匹配，并且不会触及Append节点内其他任何内容的内容，因为它们是杂耍的。懒惰因此被自然地保留下来。

(**) 2020 年编辑：这实际上意味着有一个uncons :: Dlist a -> (a, Dlist a)操作同时产生头部和新的旋转尾部，因此uncons在新尾部上是O(1)。(*)

(*) 编辑： O(1)以防最左边List节点的列表不为空。总体而言，考虑到可能嵌套在左侧的节点在第一个最左侧节点耗尽后出现Append时必须重新排列，因此对结果的所有n 个元素的访问将是O(n+ m)，其中m是空列表的数量。List

更新：历史记录：这实际上与 1977 年由 John McCarthy 处理的有效树边缘枚举问题非常相似（如果不完全相同），其gopher函数执行完全相同类型的节点重新排列（树旋转到右边）就像这里建议的tail（**）一样。

于 2017-05-12T19:36:13.170 回答
3

(++)当您以左关联方式使用它时，就会出现 的臭名昭著的坏渐近 - 也就是说，当(++)的左参数是另一个调用的结果时(++)。不过，右关联表达式运行效率很高。

更具体地说：评估m列表的左嵌套追加，例如

((ws ++ xs) ++ ys) ++ zs  -- m = 3 in this example

到 WHNF 要求你强制mthunk，因为(++)它的左参数是严格的。

case (
    case (
        case ws of { [] -> xs ; (w:ws) -> w:(ws ++ xs) }
    ) of { [] -> ys ; (x:xs) -> x:(xs ++ ys) }
) of { [] -> zs ; (y:ys) -> y:(ys ++ zs) }

通常，要全面评估n此类列表的元素，这将需要强制该堆栈mthunksn时间，对于 O(m*n) 复杂度。当整个列表是由单例列表（即(([w] ++ [x]) ++ [y]) ++ [z]）的追加构建的时，m = n成本为 O(n 2 )。

评估右嵌套追加，如

ws ++ (xs ++ (ys ++ zs))

到 WHNF 更容易（O（1））：

case ws of
    [] -> xs ++ (ys ++ zs)
    (w:ws) -> w:(ws ++ (xs ++ (ys ++ zs)))

评估n元素只需要评估nthunk，这与您期望的一样好。

差异列表通过支付少量 (O(m)) 的前期成本来自动将调用重新关联到(++).

newtype DList a = DList ([a] -> [a])
fromList xs = DList (xs ++)
toList (DList f) = f []

instance Monoid (DList a) where
    mempty = fromList []
    DList f `mappend` DList g = DList (f . g)

现在是一个左嵌套表达式，

toList (((fromList ws <> fromList xs) <> fromList ys) <> fromList zs)

以右关联方式进行评估：

((((ws ++) . (xs ++)) . (ys ++)) . (zs ++)) []

-- expand innermost (.)
(((\l0 -> ws ++ (xs ++ l0)) . (ys ++)) . (zs ++)) []

-- expand innermost (.)
((\l1 -> (\l0 -> ws ++ (xs ++ l0)) (ys ++ l1)) . (zs ++)) []
-- beta reduce
((\l1 -> ws ++ (xs ++ (ys ++ l1))) . (zs ++)) []

-- expand innermost (.)
(\l2 -> (\l1 -> ws ++ (xs ++ (ys ++ l1))) (zs ++ l2)) []
-- beta reduce
(\l2 -> ws ++ (xs ++ (ys ++ (zs ++ l2)))) []
-- beta reduce
ws ++ (xs ++ (ys ++ (zs ++ [])))

您执行 O(m) 步骤来评估组合函数，然后执行 O(n) 步骤来评估结果表达式，总复杂度为 O(m+n)，渐近优于 O(m*n)。当列表完全由单例列表的附加组成时，m = n您会得到 O(2n) ~ O(n)，这在渐近上优于 O(n 2 )。

这个技巧适用于任何Monoid.

newtype RMonoid m = RMonoid (m -> m)  -- "right-associative monoid"
toRM m = RMonoid (m <>)
fromRM (RMonoid f) = f mempty
instance Monoid m => Monoid (RMonoid m):
    mempty = toRM mempty
    RMonoid f `mappend` RMonoid g = RMonoid (f . g)

另见，例如，Codensity monad，它将这个想法应用于使用构建的一元表达式(>>=)（而不是使用构建的单曲面表达式(<>)）。

我希望我已经说服你，(++)只有在以左关联方式使用时才会导致问题。现在，您可以轻松编写一个类似列表的数据结构，其中 append 在其右参数中是严格的，因此左关联追加不是问题。

data Snoc a = Nil | Snoc (Snoc a) a

xs +++ Nil = xs
xs +++ (Snoc ys y) = Snoc (xs +++ ys) y

我们恢复左嵌套追加的 O(1) WHNF，

((ws +++ xs) +++ ys) +++ zs

case zs of
    Nil -> (ws +++ xs) +++ ys
    Snoc zs z -> Snoc ((ws +++ xs) +++ ys) +++ zs) z

但以缓慢的右嵌套追加为代价。

ws +++ (xs +++ (ys +++ zs))

case (
    case (
        case zs of { Nil -> ys ; (Snoc zs z) -> Snoc (ys +++ zs) z }
    ) of { Nil -> xs ; (Snoc ys y) -> Snoc (xs +++ ys) y }
) of { Nil -> ws ; (Snoc xs x) -> Snoc (ws +++ xs) y }

然后，当然，您最终会编写一种新类型的差异列表，它将附加到左侧的重​​新关联！

newtype LMonoid m = LMonoid (m -> m)  -- "left-associative monoid"
toLM m = LMonoid (<> m)
fromLM (LMonoid f) = f mempty
instance Monoid m => Monoid (LMonoid m):
    mempty = toLM mempty
    LMonoid f `mappend` LMonoid g = LMonoid (g . f)
于 2017-05-12T17:09:38.133 回答