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

Question

这样的结构对于实时应用程序是必要的 - 例如用户界面。(用户不在乎点击按钮需要0.1秒还是0.2秒，但如果第100次点击强制执行一个未完成的计算并需要10秒才能继续，则他们会关心。)

我正在阅读Okasaki的论文 Purely functional data structures，他描述了一种将具有分摊边界的惰性数据结构转换为具有相同每个操作的最坏情况边界的有趣通用方法。其思想是分配计算，以便在每次更新时强制执行某些未评估的thunks的一部分。

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

containers包说

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

因此，对于单个操作的最坏情况下没有保证。有严格的变体，如Data.Map.Strict，但它们在其键和值上是严格的：键和值参数在存储在映射中之前会被计算为WHNF；在结构上（可能）没有严格性的要求。

- Petr

---

您的数据结构的最坏情况渐近界限可能会或可能不会转化为实际时间行为。您正在使用垃圾收集语言，因此您的成本模型仅在分摊情况下有效。任意的GC暂停仍然是可能的。 - Philip JF

Answer 1

它的结构可能没有严格性限制。

去查找源代码，例如 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、Set 和 IntSet。

因此，通过在每次操作之前强制容器到 WHNF，你可以轻松地防止大 thunk 的构建（除了映射到/包含的值）。对于包含的值而言，避免大 thunk（时间（和空间）泄漏的常见原因）是 Data.XYZ.Strict 变体自动处理的（警告：仅在需要更多内容时才评估该值为 WHNF，例如，在操作后立即使用 deepseq 更改任何值），而这是你需要使用 Data.XYZ.Lazy 变体自己处理的。

因此，

用户不关心点击按钮需要 0.1s 还是 0.2s，但如果第 100 次点击强制执行一个未完成的惰性计算并需要 10s 执行，则他们会关心。

这是使用这些容器可以轻松避免的问题。

然而，仍有可能第100次点击的处理时间比平均值要长得多，不是由于突出的惰性计算，而是由于算法（考虑具有两个列表的经典队列实现，其中前面的列表用于通过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)），而不改变摊销成本。

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

- Daniel Fischer

---

广告队列：这正是Okasaki正在解决的问题。他在适当的时间安排反转，然后强制在每次更新时执行反转的常量部分，以便在需要反转部分时，它已经完全评估。 - Petr