9

以下程序正确终止：

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 中生成随机列表并在需要时将其传递给纯函数非常方便，我不明白为什么这不应该出现在标准库中。

4

2 回答 2

12

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

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

实际上，System.Random正是为此目的提供了函数，randoms或者randomRs代替randomand randomR。

如果出于某种原因你想自己做，你想要的本质上是一个展开。函数unfoldrfromData.List具有类型签名(b -> Maybe (a, b)) -> b -> [a]，这是不言自明的：给定一个 type 的值b，它应用该函数来获取 type 的某些内容和 typea的新生成器值b，或者Nothing指示序列的结束。

你想要一个无限的列表，所以永远不需要 return 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，它将产生一个从该种子生成的随机数的无限（和惰性）列表。

于 2010-07-29T02:22:26.230 回答
6

我会做更多这样的事情，让 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]

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

这在对先前问题的回答中得到了更好的解释：Haskell 的 mapM 不懒惰吗？

于 2010-07-29T02:20:58.620 回答