代码之家 › 专栏 › 技术社区 › Steve

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

lazy-evaluation monads haskell

8

Steve · 技术社区 · 16 年前

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

这就是我要找的。

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中生成一个随机列表,并在需要时将其传递到纯函数中,我不明白为什么这不应该在标准库中。

2 回复 | 直到 15 年前

1

5

Community Mohan Dere 9 年前

我会做一些更像这样的事情,让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]

在对前面问题的回答中可以更好地解释这一点: Is Haskell's mapM not lazy?

2

12

C. A. McCann Ravikant Cherukuri 16 年前

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

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

事实上, System.Random randoms 或 randomRs 而不是 random randomR .

如果出于某种原因你想自己做,你想要的基本上是展开 unfoldr 从 Data.List 具有类型签名 (b -> Maybe (a, b)) -> b -> [a] b ,它应用函数来获取 a ,或 Nothing 表示序列的结束。

没有什么 . 因此,部分应用到所需的范围并用 Just 给出:

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

把它放进 展开器

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

RandomGen ,它将产生一个无限的 懒惰的 )从该种子生成的随机数的列表。