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

是我在寻找的.

编辑2:在阅读了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

一般的随机数并不严格,但是monadic绑定是 - 这里的问题是mapM必须对整个列表进行排序.考虑它的类型签名,(a -> m b) -> [a] -> m [b]; 这意味着,它所做的是首先map将类型列表[a]放入类型列表中[m b],然后sequence列出该类型的结果m [b].因此,当您绑定应用结果时mapM,例如将其放在右侧<-,这意味着"将此函数映射到列表上,然后执行每个monadic操作,并将结果合并回单个列表" .如果列表是无限的,这当然不会终止.

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

事实上,System.Random提供正是为了这个目的的功能,randoms或者randomRs代替random和randomR.

如果由于某种原因你想自己做,你想要的基本上是展开.函数unfoldrfrom 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,它将产生一个从该种子生成的无限(和懒惰)随机数列表.

Answer 2

我会做更像这样的事情,让randomRs用一个初始的RandomGen来完成工作:

#! /usr/bin/env runhaskell

import Control.Monad
import System.Random


randomList :: RandomGen g => g -> [Int]
randomList = randomRs (0, 50000)

main :: IO ()
main = do
   randomInts <- liftM randomList newStdGen
   print $ take 5 randomInts

而对于懒惰,这里发生了什么是mapM是(sequence . map)

它的类型是: mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]

它正在映射函数,给出一个[m b]然后需要执行所有这些动作来制作一个m [b].这是永远无法通过无限列表的序列.

在先前的问题的答案中更好地解释了这一点:Haskell的mapM不是懒惰的吗？