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

Question

这种结构对于实时应用是必需的 - 例如用户界面.(如果点击一个按钮需要0.1秒或0.2秒,用户不在乎,但是如果第100次点击强制执行一个非常懒的计算并且需要10秒才能继续,他们会关心.)

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

我想知道,是否有任何这样的实施标准集合(的Map,Set等等)在Haskell？

该容器包装说

每项操作的申报成本是最坏情况或摊销,但即使共享结构也仍然有效.

因此无法保证单个操作的最坏情况限制.有严格的变体Data.Map.Strict,但它们的键和值严格:

键和值参数被评估为WHNF; 在将值和值存储在地图中之前,它们将被评估为WHNF.

没有关于(可能)严格的结构.

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

你看到a Map完全是脊椎严格的(并且严格按键,即使有Data.Map.Lazy),如果你将它评估为WHNF,则强制使用完整的脊椎.这同样适用于IntMapS,SetS和IntSet秒.

因此,您可以通过在每次操作之前将容器强制转换为WHNF来轻松地防止构造大型thunk(除了映射到/包含的值).对于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(大小),但它仍然是O(1)摊销的不改变摊余成本.

我不知道容器中使用的算法是否有任何此类情况,但需要注意的事项.