haskell - 差异列表的显式纯函数数据结构

Question

在 Haskell 中，difference lists , 从某种意义上说

[a] representation of a list with an efficient concatenation operation

好像是 implemented in terms of function composition .

但是，函数和(动态)函数组合也必须使用数据结构在计算机内存中以某种方式表示，这提出了如何 dlists 的问题。可以在 Haskell 中实现，而无需使用函数组合，而是通过一些基本的纯函数式基于节点的数据结构。这怎么能用与函数组合相同的性能保证来完成？

Answer 1

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

更具体地说:评估 m 的左嵌套附加列出像

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

到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此类列表的元素，这将需要强制该堆栈 m重击 n次，对于 O(m*n) 复杂度。当整个列表是从单例列表的追加构建时(即 (([w] ++ [x]) ++ [y]) ++ [z] )， m = n所以成本是 O(n2)。

评估右嵌套的追加，如

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

到 WHNF 更容易(O(1)):

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

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

差异列表通过支付少量 (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(n2) 渐进好。

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

另见，例如， the Codensity monad ，它将这个想法应用于使用 (>>=) 构建的 monadic 表达式(而不是使用 (<>) 构建的幺半群表达式)。

我希望我已经说服了您 (++)仅在以左关联方式使用时才会导致问题。现在，您可以轻松编写一个类似列表的数据结构，它的右参数 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)