这种结构对于实时应用是必需的 - 例如用户界面。 （如果点击一个按钮需要0.1秒或0.2秒，用户不在乎，但是如果第100次点击强制执行一个非常懒的计算并且需要10秒才能继续，他们会关心。）
我正在读冈崎的论文 纯功能数据结构 他描述了一种有趣的通用方法，用于将带有摊销边界的惰性数据结构转换为具有相同结构的结构 最坏情况的界限 一切 手术。我们的想法是分配计算，以便在每次更新时强制部分未评估的thunk。
我想知道，是否有任何此类标准集合的实现（Map， Set等等）在Haskell？
该 集装箱 包说
每项操作的申报成本是最坏情况或摊销，但即使共享结构也仍然有效。
因此无法保证单个操作的最坏情况限制。有严格的变种，如 Data.Map.Strict，但他们的关键和价值观严格：
密钥和值参数被评估为WHNF;在将值和值存储在地图中之前，它们将被评估为WHNF。
关于（可能）严格的结构没有任何意义。
关于（可能）严格的结构没有任何意义。
去寻找来源，例如对于 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，那么完整的脊柱就会被迫。这同样适用 IntMapS， Sets和 IntSet秒。
因此，您可以通过在每次操作之前将容器强制转换为WHNF来轻松地防止构造大型thunk（除了映射到/包含的值）。防止所包含的值的大th [时间（和空间）泄漏的常见原因]是自动的 Data.XYZ.Strict 变体（警告：这些值只评估为WHNF，如果你需要更多，你必须自己做，例如 deepseq在手术后immediatley的任何改变的值），你需要处理自己的事情 Data.XYZ.Lazy 变种。
从而
如果单击按钮需要0.1秒或0.2秒，用户并不在意，但是如果第100次单击强制执行一个未完成的延迟计算并需要10秒才能继续，他们会关心。
这些容器是一个容易避免的问题。
但是，它仍然可能是第100次点击 许多 比平均更长的处理，不是由于优秀的懒惰计算，而是由于算法（考虑经典队列实现有两个列表，前面，你通过 dequeue (Q (x:xs) ys) = (x, Q xs ys) 在O（1），和你的后面 enqueue y (Q xs ys) = Q xs (y:ys) 在O（1）中，除了当前面的清单是空的并且后面需要先反转，然后它的O（1）仍然是摊销而不改变摊余成本时，出列需要O（大小）。
我不知道是否使用了算法 集装箱 有任何这样的情况，但这是值得注意的。