这样的结构对于实时应用程序(例如用户界面(是必需的。(用户不在乎单击按钮需要 0.1 秒还是 0.2 秒，但他们确实关心第 100 次点击是否强制完成出色的延迟计算并需要 10 秒才能继续。
我正在阅读冈崎的论文纯函数式数据结构，他描述了一种有趣的通用方法，该方法将具有摊销边界的惰性数据结构转换为每个操作具有相同最坏情况边界的结构。这个想法是分发计算，以便在每次更新时强制使用某些未评估的thunks。
我想知道，在 Haskell 中是否有这样的标准集合(Map、Set 等(的实现？
容器包说
每项操作的申报成本要么是最坏情况，要么是摊销的，但即使结构是共享的，仍然有效。
因此，无法保证单个操作的最坏情况边界。有严格的变体，如 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，整个脊椎是被迫的。这同样适用于IntMap s，Set s和IntSet s。
因此，您可以通过在每次操作之前强制容器到 WHNF 来轻松防止构造大型故障(映射到/包含的值除外(。对于Data.XYZ.Strict变体，防止所包含值[时间(和空间(泄漏的常见原因]出现大混乱是自动的(警告：这些值仅评估为WHNF，如果您需要更多，则必须自己完成，例如 deepseq操作后立即处理任何更改的值(，您需要使用Data.XYZ.Lazy变体来处理自己。
因此
用户不在乎单击按钮需要 0.1 秒还是 0.2 秒，但他们确实关心第 100 次点击是否强制完成出色的延迟计算并需要 10 秒才能继续。
是这些容器很容易避免的问题。
但是，第 100 次点击的处理时间可能比平均值长得多，这不是由于出色的惰性计算，而是由于算法(考虑具有两个列表的经典队列实现，前面，您在 O(1( 中按dequeue (Q (x:xs) ys) = (x, Q xs ys)将元素取消排队，后部在 O(1( 中enqueue y (Q xs ys) = Q xs (y:ys)， 好吧，除了当前面的列表为空并且后面需要先反转时，出列需要 O(size(，但它仍然是 O(1( 摊销的(，而不会改变摊销成本。
我不知道容器中使用的算法是否有这种情况，但这是需要注意的。