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屋!