Haskell中的mapM是严格的吗？为什么这个程序得到堆栈溢出？ [英] Is mapM in Haskell strict? Why does this program get a stack overflow?

问题描述

  import System.Random 
 
 randomList = mapM（\\ （randomR（0,50000 :: Int）））[0..5000] 
 
 main = do 
 randomInts<  -  randomList 
 print $采取5 randomInts 
  

跑步：

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

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

 （$ 50000 :: Int））[0 ..] 
 
 main = do 
 randomInts<  -  randomList 
 print $ take 5 randomInts 
  

正在运行，

  $ ./test 
堆栈空间溢出：当前大小8388608字节。 
使用'+ RTS -Ksize -RTS'来增加它。 
  

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

谢谢。

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

编辑：一些更多的阅读表明，该函数

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

就是我想要的。

编辑2：在阅读camccann的回答后，我意识到 getStdGen



  import System.Random 
 
 randomList :: Random a => a  - > a  - > IO [a] 
 randomList rg = 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中生成一个随机列表，并在需要时将它传递给一个纯函数，我不明白为什么它不应该在标准库中。 / p>

解决方案

我会做更多这样的事情，让randomRs使用初始的RandomGen完成工作：

 ＃！ / usr / bin / env runhaskell 
 
 import Control.Monad 
 import System.Random 
 
 
 randomList :: RandomGen g => g  - > [Int] 
 randomList = randomRs（0,50000）
 $ b $ main main :: IO（）
 main = do 
 randomInts<  -  liftM randomList newStdGen 
打印$ take 5 randomInts 
  

至于懒惰，这里发生的是 mapM 是（sequence。map）

它的类型是： mapM ::（Monad m）=> （a - > m b） - > [a] - > m [b]

它映射函数，给出 [mb] 和那么需要执行所有这些操作来创建 m [b] 。这是从来没有通过无限列表的序列。

这在前面问题的答案中有更好的解释： Haskell的mapM不懒惰吗？

The following program terminates correctly:

import System.Random

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

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

Running:

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

However, feeding it with an infinite list, the program never terminates, and when compiled, eventually gives a stack overflow error!

import System.Random

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

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

Running,

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

I expected the program to lazily evaluate getStdRandom each time I pick an item off the list, finishing after doing so 5 times. Why is it trying to evaluate the whole list?

Thanks.

Is there a better way to get an infinite list of random numbers? I want to pass this list into a pure function.

EDIT: Some more reading revealed that the function

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

is what I was looking for.

EDIT2: after reading camccann's answer, I realized that getStdGen is getting a new seed on every call. Instead, better to use this function as a simple one-shot random list generator:

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

But I still don't understand why my mapM call did not terminate. Evidently not related to random numbers, but something to do with mapM maybe.

For example, I found that the following also does not terminate:

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

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

What gives? By the way, IMHO, the above randomInts function should be in System.Random. It's extremely convenient to be able to very simply generate a random list in the IO monad and pass it into a pure function when needed, I don't see why this should not be in the standard library.

解决方案

I would do something more like this, letting randomRs do the work with an initial 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

As for the laziness, what's happening here is that mapM is (sequence . map)

Its type is: mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]

It's mapping the function, giving a [m b] and then needs to execute all those actions to make an m [b]. It's the sequence that'll never get through the infinite list.

This is explained better in the answers to a prior question: Is Haskell's mapM not lazy?

这篇关于Haskell中的mapM是严格的吗？为什么这个程序得到堆栈溢出？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！