haskell - Haskell中的mapM严格吗？为什么这个程序会出现堆栈溢出？

Question

以下程序正确终止:

import System.Random

randomList = mapM (\_->getStdRandom (randomR (0, 50000::Int))) [0..5000]

main = do
  randomInts <- randomList
  print $ take 5 randomInts

运行:

$ runhaskell test.hs
[26156,7258,29057,40002,26339]

然而，给它一个无限列表，程序永远不会终止，并且在编译时，最终会出现堆栈溢出错误!

import System.Random

randomList = mapM (\_->getStdRandom (randomR (0, 50000::Int))) [0..]

main = do
  randomInts <- randomList
  print $ take 5 randomInts

运行，

$ ./test
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

我希望程序能够懒惰地评估 getStdRandom每次我从列表中选择一个项目，在这样做 5 次后完成。为什么要评估整个列表？

谢谢。

有没有更好的方法来获得无限的随机数列表？我想将此列表传递给纯函数。

编辑:更多阅读表明该功能

randomList r = do g <- getStdGen
                  return $ randomRs r g

是我一直在寻找的。

EDIT2:阅读 camccann 的回答后，我意识到 getStdGen每次通话都会获得新种子。相反，最好将此函数用作简单的一次性随机列表生成器:

import System.Random

randomList :: Random a => a -> a -> IO [a]
randomList r g = do s <- newStdGen
                    return $ randomRs (r,g) s

main = do r <- randomList 0 (50::Int)
          print $ take 5 r

但是我还是不明白为什么我的 mapM通话没有终止。显然与随机数无关，但与 mapM 有关也许。

例如，我发现以下内容也不会终止:

randomList = mapM (\_->return 0) [0..]

main = do
  randomInts <- randomList
  print $ take 50000 randomInts

是什么赋予了？顺便说一句，恕我直言，以上 randomInts函数应该在 System.Random .能够非常简单地在 IO monad 中生成随机列表并在需要时将其传递给纯函数非常方便，我不明白为什么这不应该出现在标准库中。

Answer 1

随机数一般不严格，但一元绑定(bind)是——这里的问题是 mapM必须对整个列表进行排序。考虑它的类型签名，(a -> m b) -> [a] -> m [b] ;正如这所暗示的，它首先要做的是map类型列表[a]进入类型列表[m b] ，然后 sequence该列表获得类型为 m [b] 的结果.所以，当你绑定(bind)应用 mapM 的结果时，例如将其放在 <- 的右侧，这意味着“将此函数映射到列表上，然后执行每个单子(monad)操作，并将结果组合回单个列表”。如果列表是无限的，这当然不会终止。

如果您只是想要一个随机数流，则需要生成列表而不为每个数字使用 monad。我不完全确定你为什么使用你的设计，但基本思想是:给定一个种子值，使用伪随机数生成器产生一对 1) 一个随机数 2) 一个新种子，然后用新种子重复。当然，任何给定的种子每次都会提供相同的序列。因此，您可以使用函数 getStdGen ，这将在 IO 中提供新鲜种子单子(monad);然后，您可以使用该种子在完全纯代码中创建无限序列。

事实上，System.Random正是为此目的提供功能，randoms或 randomRs而不是 random和 randomR .

如果出于某种原因你想自己做，你想要的本质上是一个展开。函数unfoldr来自 Data.List具有类型签名 (b -> Maybe (a, b)) -> b -> [a] ，这是不言自明的:给定一个类型为 b 的值, 它应用函数来获取 a 类型的任何东西和 b 类型的新生成器值, 或 Nothing表示序列的结束。

你想要一个无限列表，所以永远不需要返回 Nothing .因此，部分应用 randomR到所需的范围并将其与 Just 组合给出了这个:

Just . randomR (0, 50000::Int) :: (RandomGen a) => a -> Maybe (Int, a)

将其输入 unfoldr给出了这个:

unfoldr (Just . randomR (0, 50000::Int)) :: (RandomGen a) => a -> [Int]

...正如它声称的那样:给定 RandomGen 的实例，它将生成从该种子生成的随机数的无限(和惰性)列表。