Haskell 集合可以保证每个操作的最坏情况范围？

这种结构对于实时应用程序（例如用户界面）是必要的。 （用户并不关心单击按钮是否需要 0.1 秒或 0.2 秒，但他们确实关心第 100 次单击是否会强制执行出色的惰性计算并需要 10 秒才能继续。）

我在读冈崎的论文纯函数式数据结构 http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf他描述了一种有趣的通用方法，用于将具有摊销界限的惰性数据结构转换为具有相同结构的结构最坏情况的界限every手术。这个想法是分布式计算，以便在每次更新时强制执行未评估的重击的某些部分。

我想知道，是否有这样的标准集合的实现（Map, Set等）在哈斯克尔？

The 容器 http://hackage.haskell.org/package/containers-0.5.0.0包裹说

每个操作的声明成本要么是最坏情况，要么是摊销的，但即使共享结构也仍然有效。

因此无法保证单个操作的最坏情况边界。有严格的变体，例如Data.Map.Strict，但他们对键和值很严格：

键和值参数被评估为 WHNF；键和值在存储到映射之前会被评估为 WHNF。

其结构没有（可能的）严格性。

其结构没有（可能的）严格性。

去寻找来源，例如为了Data.Map.Map http://hackage.haskell.org/packages/archive/containers/0.5.0.0/doc/html/src/Data-Map-Base.html#Map

-- See Note: Order of constructors
data Map k a  = Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a)
              | Tip

你看到一个Map完全是脊椎严格的（并且在琴键上也严格，即使Data.Map.Lazy），如果评估为WHNF，则整个脊柱受力。这同样适用于IntMaps, Sets and IntSets.

因此，您可以通过在每次操作之前强制容器进行 WHNF 来轻松防止构建大型 thunk（映射到/包含的值除外）。对于所包含的值，防止大的重击[时间（和空间）泄漏的常见原因]是自动的Data.XYZ.Strict变体（警告：这些值仅评估为 WHNF，如果您需要更多，您必须自己完成，例如deepseq操作后立即更改值），您需要自己处理Data.XYZ.Lazy变种。

Thus

用户并不关心单击按钮是否需要 0.1 秒或 0.2 秒，但他们关心第 100 次单击是否会强制执行出色的惰性计算并需要 10 秒才能继续。

对于这些容器来说这是一个很容易避免的问题。

然而，第 100 次点击仍然可能需要much处理时间比平均值更长，不是由于出色的惰性计算，而是由于算法（考虑具有两个列表的经典队列实现，前面，您通过以下方式将元素出列）dequeue (Q (x:xs) ys) = (x, Q xs ys)在 O(1) 中，而后面你enqueue y (Q xs ys) = Q xs (y:ys)在 O(1) 中，好吧，除了当前面的列表为空并且需要先反转后面的列表时，出队需要 O(size)，但它仍然是 O(1) 摊销）而不改变摊余成本。

不知道用的算法有没有容器 http://hackage.haskell.org/package/containers确实有这样的案例，但需要注意。