Haskell回避概率数据结构？

Question

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

Haskell人员是否远离这些数据结构,因为它们不可能纯粹实现它们？Haskell如何处理它们？

Answer 1

伪随机数发生器当然可以在外部使用IO,通过简单地存储当前发生器值以及概率纯数据结构并在构造修改版本时更新它.这样做的缺点是PRNG将比不纯的程序更明确地确定性,因为单个数据结构之外的任何内容都不会更新它.如果只有统计特性很重要,这不会引起任何问题,但可能引起关注.

在另一方面,隐藏不纯的PRNG可以说是一个合理的使用unsafePerformIO作为加内什·锡坦帕勒姆的答案.这明显违反了引用透明度,但仅限于PRNG将返回不可预测的,不一致的值 - 这是重点!但是,仍然需要注意,因为编译器可能对代码做出错误的假设,因为它看起来很纯粹.

但实际上,这两种方法都不是非常有吸引力.使用unsafePerformIO不满意且有潜在危险.线程化PRNG状态很容易,但对使用它的任何计算都施加了(可能是虚假的)严格排序.Haskell程序员不会轻易放弃安全性和懒惰性(这是正确的!),当然数据结构限制为IO实用性有限.所以,为了回答你的部分问题,这就是为什么Haskell程序员可能会避免这种结构.

至于"Haskell如何处理"这类事情,我建议这是一个错误的问题.

它真正归结为许多数据结构和算法隐含地假设(并优化)命令性的,不纯的,严格的语言,虽然在Haskell中实现它们当然是可能的,但它很少是可取的,因为(甚至忽略了内部实现)使用它们会给你的代码带来一种非常不恰当的结构和方法.此外,由于Haskell违反了这些隐含的假设,因此性能通常会降低(有时非常糟糕).

要意识到的是,算法和数据结构是一种手段,而不是目的.这是很少所需单个具体实施的情况-什么是需要的是一般的某些性能特性.寻找提供所需特性的数据结构/算法,同时也是惯用的Haskell几乎总是一个更好的计划,并且可能比尝试将严格的命令挂钩插入惰性功能洞更好.

这个错误可能最常见于那些从未遇到过用哈希表无法解决的问题的程序员子集,但这种习惯很容易让我们很多人陷入困境.正确的方法是停止思考"如何在Haskell中实现此解决方案",而是"在Haskell中解决我的问题的最佳方法是什么".你可能会惊讶于答案的不同之处; 我知道我经常这样!

Answer 2

跳过列表可以纯粹实现 - 只需将当前种子封装在跳过列表本身的状态中.

data SkipList a = SkipList StdGen (Node a)
data Node a = ...

这可能会使您面临一些针对"真实"跳过列表不切实际的复杂性攻击,因为您可以探测退化插入顺序并重放针对同一种子的攻击,但它可以让您在对抗使用时获得结构的好处不是问题.

你也可以依靠unsafePerformIO精心设计的副作用 - 看似纯粹的界面.虽然不可否认它在内部并不纯净,但界面给人以纯净的外观.

也就是说,跳过列表的许多经典性能优势来自于它们可以非持久地实现,并且排除了功能接口.

Answer 3

由于跳过列表具有纯接口,因此在IO内部使用实现并将其包装unsafePerformIO为接口是有效的.这简单地将"正确"的负担从语言转移到程序员(负担总是存在于不纯的语言中).