haskell - (已编辑)如何在没有 IO 的情况下在 Haskell 中获取随机数

Question

我想要一个函数在每次调用中返回不同的 stdGen 而无需 IO。我尝试使用 unsafePerformIO，如以下代码。

import System.IO.Unsafe
import System.Random

myStdGen :: StdGen
myStdGen = unsafePerformIO getStdGen

但是当我尝试在 ghci 中调用 myStdGen 时，我总是得到相同的值。我是否滥用了 unsafePerformIO？或者还有其他方法可以实现我的目标吗？

编辑抱歉，我想我应该更准确地描述我的问题。

实际上，我正在实现treap数据结构的变体，它需要特殊的“合并”操作。它依赖于一定的随机性来保证摊销 O(log n) 的预期时间复杂度。

我尝试使用像(Tree, StdGen)这样的对来为每个trap保留随机生成器。当向treap插入新数据时，我会使用random为新节点提供随机值，然后更新我的生成器。但我遇到了一个问题。我有一个名为 empty 的函数，它将返回一个空的treap，并且我使用上面的函数 myStdGen 来获取该treap 的随机生成器。但是，如果我有两个空的trap，它们的StdGen 将是相同的。因此，在我向两个trap中插入数据之后，当我想要合并它们时，它们的随机值也将是相同的。因此，我失去了我所依赖的随机性。

这就是为什么我想要一个某种程度的“全局”随机生成器，它为每个调用生成不同的 StdGen ，以便每个空的treap 可以有不同的 StdGen 。

Answer 1

Do I abused unsafePerformIO

哎呀，是的! “纯函数的显着特征”是

• 无副作用
• 参照透明，即结果的每次后续评估必须产生相同的结果。

事实上有一种方法可以实现你的“目标”，但这个想法是错误的。

myStdGen :: () -> StdGen
myStdGen () = unsafePerformIO getStdGen

因为这是一个(无用的)函数调用，而不是 CAF ，它将在每次调用时分别评估 IO 操作。

不过，我认为编译器可以自由地对其进行优化，因此绝对不要依赖它。

编辑在尝试时我注意到getStdGen本身在给定进程中使用时总是给出相同的生成器，所以即使上面会使用更合理的类型，它也不会工作。

<小时/>请注意，在算法等中正确使用伪随机性并不需要到处使用 IO - 例如，您可以手动为 StdGen 播种，然后使用 split< 正确传播它 等等。处理这个问题的更好方法是使用 randomness monad 。整个程序将始终产生相同的结果，但内部具有有效工作所需的所有不同的随机数。

或者，您可以从 IO 获取生成器，但仍然用纯随机 monad 而不是 IO 编写算法。

<小时/>

还有另一种方法可以在完全纯的算法中获得“随机性”:要求输入为 Hashable !然后，您可以有效地使用任何函数参数作为随机种子。这是一个有点奇怪的解决方案，但可能适用于您的treap应用程序(尽管我认为有些人不会再将其分类为treap，而是作为一种特殊类型的 HashMap )。