这样的结构对于实时应用程序是必要的 - 例如用户界面。(用户不在乎点击按钮需要0.1秒还是0.2秒,但如果第100次点击强制执行一个未完成的计算并需要10秒才能继续,则他们会关心。)
我正在阅读Okasaki的论文 Purely functional data structures,他描述了一种将具有分摊边界的惰性数据结构转换为具有相同每个操作的最坏情况边界的有趣通用方法。其思想是分配计算,以便在每次更新时强制执行某些未评估的thunks的一部分。
我想知道,是否有Haskell中标准集合(Map
,Set
等)的此类实现?
因此,对于单个操作的最坏情况下没有保证。有严格的变体,如每个操作的声明成本都是最坏情况或分摊成本,但即使结构共享,仍然有效。
Data.Map.Strict
,但它们在其键和值上是严格的:键和值参数在存储在映射中之前会被计算为WHNF;在结构上(可能)没有严格性的要求。