差异列表的显式纯功能数据结构

Question

在Haskell，差异表中的感

[a]使用有效的串联操作表示列表

似乎是在功能组成上实现的。

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

Answer 1

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

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

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

to WHNF 要求你强制m重击，因为(++)它的左参数是严格的。

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此类列表的元素，这需要强制执行mthunkn次堆栈，复杂度为 O(m*n)。当整个列表是从单例列表的追加（即(([w] ++ [x]) ++ [y]) ++ [z]）构建时，m = n因此成本是 O(n ² )。

评估右嵌套附加，例如

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 ² ) 渐近更好。

这个技巧适用于任何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)

例如，另请参见Co密度 monad，它将这一思想应用于使用 构建的一元表达式(>>=)（而不是使用 构建的幺元表达式(<>)）。

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

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)