Haskell 回避概率数据结构？

Question

如果您搜索 Haskell 中实现的跳过列表，您不会找到很多。它是一个需要随机数生成器的概率数据结构，这意味着任何这些结构都需要在 IO monad 中运行。

Haskell 人员是否因为无法纯粹实现它们而远离这些数据结构？ Haskell 如何处理它们？

Answer 1

伪随机数生成器当然可以在IO之外使用，只需将当前生成器值与概率纯数据结构一起存储，并在构造修改版本时更新它即可。这样做的缺点是，PRNG 比不纯的程序具有更明显的确定性，因为单一数据结构之外的任何内容都不会更新它。如果只有统计属性很重要，那么这不会造成问题，但否则可能会引起关注。

另一方面，隐藏不纯的 PRNG 可以说是 unsafePerformIO 的合理使用，如 Ganesh Sittampalam 的回答所示。这公然违反​​了引用透明度，但仅限于 PRNG 将返回不可预测的、不一致的值——这就是重点!但是，仍然需要小心，因为编译器可能会对代码做出错误的假设，因为它看起来是纯粹的。

但实际上，这两种方法都没有太大吸引力。使用 unsafePerformIO 并不令人满意，而且有潜在危险。对 PRNG 状态进行线程化很容易，但会对使用它的任何计算施加严格的排序(可能是虚假的)。 Haskell 程序员不会轻易放弃安全性和懒惰(这是正确的!)，当然，仅限于 IO 的数据结构的实用性也很有限。因此，为了回答您的部分问题，这就是 Haskell 程序员可能会避免此类结构的原因。

<小时/>

至于“Haskell 如何处理”此类事情，我认为这是问错的问题。

真正归结为许多数据结构和算法隐含假设(并优化)一种命令式、不纯粹、严格的语言，尽管它肯定是<可能在 Haskell 中实现这些，但很少需要，因为(即使忽略内部实现)使用它们会给您的代码强加一种非常不惯用的结构和方法。此外，由于 Haskell 违反了这些隐含的假设，性能常常会下降(有时甚至严重)。

要认识到的是，算法和数据结构只是手段，而不是目的。很少有需要单个特定实现的情况 - 需要通常是某些性能特征。寻找既能提供所需特性又符合 Haskell 习惯的数据结构/算法几乎总是一个更好的计划，并且可能比试图将严格的命令式 Hook 塞进惰性功能漏洞表现得更好。

这个错误可能最常见于从未遇到过用哈希表无法解决的问题的程序员子集，但对于我们许多人来说，这个习惯很容易陷入。正确的方法是停止思考“我如何在Haskell中实现这个解决方案”，而是“在Haskell中解决我的问题的最佳方法是什么”。您可能会惊讶于答案经常不同；我知道我经常这样!