Haskell 集合保证每个操作的最坏情况界限？

Question

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

我在看冈崎的论文Purely functional data structures他描述了一种有趣的通用方法，用于将具有摊销边界的惰性数据结构转换为具有相同 的结构。每个操作的最坏情况界限 .这个想法是分配计算，以便在每次更新时强制执行一些未评估的 thunk。

我想知道，Haskell 中是否有任何标准集合( Map 、 Set 等)的实现？

containers包说

The declared cost of each operation is either worst-case or amortized, but remains valid even if structures are shared.

因此不能保证单个操作的最坏情况界限。有严格的变体，如 Data.Map.Strict ，但它们的键和值很严格:

Key and value arguments are evaluated to WHNF; Keys and values are evaluated to WHNF before they are stored in the map.

它的结构没有(可能的)严格性。

Answer 1

there is nothing about (possible) strictness of its structure.

去寻找来源，例如对于 Data.Map.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，则强制使用完整的脊椎。这同样适用于 IntMap s、Set s 和 IntSet s。

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

因此

Users don't care if clicking a button takes 0.1s or 0.2s, but they do care if the 100th click forces an outstanding lazy computation and takes 10s to proceed.

是这些容器很容易避免的问题。

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

我不知道 containers 中使用的算法是否有这种情况，但这是需要注意的。