Haskell中的严格数据结构库

存在哪些实现严格数据结构的库？具体来说，我正在寻找严格的名单和严格的设置。Haskell中的严格数据结构库

免责声明：

我知道deepseq的。这非常有用，但是它增加了每次使用deepseq时可能遍历整个数据结构的开销（可能不止一次）。
我知道，严格的容器，如数据结构不确保它包含将全面评估一切，但结构本身应该是严格的，比如：
```
data StrictList a = !a :$ !(StrictList a) | Empty 
```
（在这里，包含的元素在WHNF中，并且可能没有完全评估，但是列表的结构是。例如，无限列表将是非终止值。）
我知道关于hackage上的'strict'包，但它有一个非常有限的 d套严格的数据结构。它不包含严格的列表或集。
写作严格列出自己似乎令人惊讶的简单（我爱GHC的扩展导出函子，Traversable的和可折叠的，顺便说一句。），但它仍然好像这将是一个单独的库做得更好。而集合的高效实现对我来说似乎并不重要。

2011-11-14 shahn

为什么你需要一个严格的结构？ – fuz

@FUZxxl确保毫不拖延地评估事物通常可以减少空间使用并使计算速度更快。它也可能具有相反的效果，所以懒惰的结构也很重要。为了高效的代码，你需要两个（并且必须知道/找出在哪里使用）。 –

@FUZxxl：我在一个集合上做类似状态monad的事情，我会经常插入和删除集合中的元素，但不会评估集合一段时间。这导致了空间泄漏，这可以通过严格的脊柱（谢谢John L）数据结构来解决。 – shahn

的containers包（随GHC）很快就会有严格的设置和地图变种（我不知道他们将被包含在GHC-7.4，但我们有理由希望）。因此，严格的Sets和Maps的高效实现即将开始。正如你所说的那样，严格的列表仍然是一个hackage包，提供它们会很好，所以不是每个人都必须自己做。你还需要什么？

来源

2011-11-14 16:20:27

听起来不错。列表和集是我需要的（现在）。 – shahn

对于你的第二点，我最常见的术语是脊椎严格。

对于脊柱严格列表，您可以使用Data.Seq.Sequence（来自容器）或Data.Vector（来自vector）。两者都不是一个清单，但是根据你在做什么（或两者）可能会更好。序列提供了O（1）cons和snoc，能够非常快速地访问结构的任何一端。 Vector的性能与数组类似。如果你想要一个更类似于Sequence的列表界面，你可以考虑ListLike包（也有一个用于向量的ListLike接口，但它不太有用，因为Vector自己提供了一个相当全面的接口）。两者都是脊椎严密的。

对于严格设置，您可以尝试unordered-containers，该设置还提供严格的地图。

来源

2011-11-14 19:28:55

这是很好的建议。 – shahn

Spine-strict的意思是，那些元素将被评估为WHNF（就像我在上面的StrictList例子中那样）？那么，你能删除第一个感叹号，仍然称它为脊椎严格吗？ – shahn

@shahn：spine-strict意味着容器的结构将被完全评估，但可能根本不评估这些元素。所以是的，你可以删除你的例子中的第一个感叹号，并仍然是脊椎严格的。 –

Haskell中的严格数据结构库

回答

相关问题