haskell - 功能阵列倍增堆栈的摊销

Question

我正在玩弄紧凑堆栈的想法——随着它的大小增加，它的空间要求接近数组的要求。候选结构:

data Stack a
  = Empty
  | Zero (Stack a)
  | One !(SmallArray a) (Stack a)
  | Two !(SmallArray a) !(SmallArray a) (Stack a)
-- Invariant: the array size at depth `n` is `2^n`.

push :: a -> Stack a -> Stack a
push = pushA . pure

pushA :: SmallArray a -> Stack a -> Stack a
pushA sa Empty = One sa Empty
pushA sa (Zero more) = One sa more
pushA sa1 (One sa2 more) = Two sa1 sa2 more
pushA sa1 (Two sa2 sa3 more) = One sa1 (pushA (sa2 <> sa3) more)

pop :: Stack a -> Maybe (a, Stack a)
pop stk = do
  (sa, stk') <- popA stk
  hd <- indexSmallArrayM sa 0
  Just (hd, stk')

popA :: Stack a -> Maybe (SmallArray a, Stack a)
popA Empty = Nothing
popA (Zero more) = do
  (sa, more') <- popA more
  let !(sa1, sa2) = -- split sa in two
  Just (sa1, One sa2 more')
popA (One sa more) = Just (sa, Zero more)
popA (Two sa1 sa2 more) = Just (sa1, One sa2 more)

一些数值实验表明我可以得到 O(log n) n 序列的每次操作平均成本插入。但是是否可以将这种结构分析为具有 O(log n)每次推送或弹出的成本？或者如果没有，可以为类似的结构做到这一点吗？我一直无法找到合适的借方不变量。棘手的情况似乎是 Two 的序列节点后跟 One节点，但我可能只是在接近这一切都是错误的。

Answer 1

我相信我已经找到了办法。我在问题中建议的数字系统结果不是正确的。不支持 O(log n) pop (或者至少不会简单地这样做)。我们可以通过从 0/1/2 冗余二进制切换到 1/2/3 冗余二进制来修补这个问题。

-- Note the lazy field in the Two constructor.
data Stack a
  = Empty
  | One !(SmallArray a) !(Stack a)
  | Two !(SmallArray a) !(SmallArray a) (Stack a)
  | Three !(SmallArray a) !(SmallArray a) !(SmallArray a) !(Stack a)

push :: a -> Stack a -> Stack a
push = pushA . pure

pushA :: SmallArray a -> Stack a -> Stack a
pushA sa Empty = One sa Empty
pushA sa1 (One sa2 more) = Two sa1 sa2 more
pushA sa1 (Two sa2 sa3 more) = Three sa1 sa2 sa3 more
pushA sa1 (Three sa2 sa3 sa4 more) = Two sa1 sa2 (pushA (sa3 <> sa4) more)

pop :: Stack a -> Maybe (a, Stack a)
pop stk = do
  ConsA sa stk' <- pure $ popA stk
  hd <- indexSmallArrayM sa 0
  Just (hd, stk')

data ViewA a = EmptyA | ConsA !(SmallArray a) (Stack a)

popA :: Stack a -> ViewA a
popA Empty = EmptyA
popA (Three sa1 sa2 sa3 more) = ConsA sa1 (Two sa2 sa3 more)
popA (Two sa1 sa2 more) = ConsA sa1 (One sa2 more)
popA (One sa more) = ConsA sa $
  case popA more of
    EmptyA -> Empty
    ConsA sa1 more' -> Two sa2 sa3 more'
      where
        len' = sizeofSmallArray sa1 `quot` 2
        sa2 = cloneSmallArray sa1 0 len'
        sa3 = cloneSmallArray sa1 len' len'

证明这具有所需的摊销界限的第一个重要步骤是选择借方不变量[*]。这让我坚持了很长一段时间，但我想我已经明白了。
借方不变量 : 我们允许懒惰的 Stack在 Two节点与存储在其中的元素一样多的借方以及所有更早的 Two节点。
定理 push和 pop运行 O(log n)摊销时间。
校样草图
推
我们依次考虑每种情况。

Empty总是微不足道的。

One : 我们在下面增加借方津贴。

Two :我们将以下节点的借方津贴减少 1 个单位。我们支付 O(log n)以清偿多余的借方。

Three : 这是 push 的棘手情况.我们有一些 Three节点后跟别的东西。对于每个 Three节点，我们暂停 s阵列加倍工作。我们使用从新的 Two 中的元素中获得的额外借方津贴来支付这笔费用。节点。当我们到达 Three 的末尾时链，我们需要做一些有趣的事情。我们可能需要下面的全部借记限额，因此我们使用借记传递将最终数组附加的借记分散到所有早期节点。
最后，我们有 Empty , One , 或 Two .如果我们有 Empty或 One ，我们完成了。如果我们有 Two ，然后将其更改为 Three减少下面的借方津贴。但我们也从以下所有 Three 中获得借方津贴。已更改为 Two 的 s !我们的净损失借方准备金只有 1，所以我们是黄金。

流行音乐
我们再次按案例进行。

Empty是微不足道的。

Three : 我们在下面增加借方津贴。

Two :我们将某些节点的借方津贴减少 1 个单位；支付 O(log n) 以偿还多余的借方。

One : 这个是硬道理。我们有一些 One节点后跟别的东西。对于每个 One ，我们执行拆分。我们通过借记来支付那些，从根本上消除那些。最后，我们遇到了类似于 push 的情况。 : 棘手的案例以 Two 结尾, 我们使用的事实是所有新的 Two s赔付最后的损失Two .

紧凑
人们可能会担心结构中可能会积累足够多的 thunk，从而否定基于数组的表示的紧凑性。幸运的是，情况并非如此。 thunk 只能出现在 Stack在 Two节点。但是对该节点的任何操作都会将其变成 One或 Three , 强制 Stack .因此，thunk 永远不会在链中累积，并且每个节点永远不会超过一个 thunk。
[*] 冈崎，C.(1998 年)。纯函数式数据结构。剑桥:剑桥大学出版社。 doi:10.1017/CBO9780511530104 ，或阅读他的 thesis 的相关部分在线的。