11

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

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

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

容器包装说

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

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

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

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

4

1 回答 1

11

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

去寻找来源，例如Data.Map.Map

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

您会看到 aMap完全是脊椎严格的（并且在键中是严格的，即使使用Data.Map.Lazy），如果您将其评估为 WHNF，则强制执行完整的脊椎。IntMaps、Sets 和s 也是如此IntSet。

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

因此

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

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

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

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

于 2012-09-12T17:53:18.357 回答