4

我想用 Haskell 生成一个包含 26 个随机整数的列表，总和为 301。我写了以下内容：

import System.Random

f 1 sum = [sum]
f n sum = m : (f (n-1) (sum-m))
    where m = randomRIO (0,sum)

但它无法编译！我对IO感到困惑！

Occurs check: cannot construct the infinite type: a1 = IO a1
In the first argument of `(:)', namely `m'
In the expression: m : (f (n - 1) (sum - m))
In an equation for `f':
    f n sum
      = m : (f (n - 1) (sum - m))
      where
          m = randomRIO (0, sum)
4

4 回答 4

8

在这种情况下，错误消息有些令人困惑，但关键是您需要在IOmonad 中工作，因为它使用randomRIOwhich is in IO，并且（根据设计）无法IO从非代码运行IO代码。

f 1 sum = return [sum]
f n sum = do
  x  <- randomRIO (0, sum)
  xs <- f (n - 1) (sum - x)
  return (x : xs)
于 2012-11-02T08:58:10.020 回答
5

除了锤子写的内容之外，如果您编写f函数所需的类型，错误消息会变得更加清晰：

f :: Int -> Int -> [Int]
f 1 sum = [sum]
f n sum = m : (f (n-1) (sum-m))
    where m = randomRIO (0,sum)

给出错误：

Couldn't match expected type `Int' with actual type `IO Int'
    In the first argument of `(:)', namely `m'
    In the expression: m : (f (n - 1) (sum - m))
    In an equation for `f':
        f n sum
          = m : (f (n - 1) (sum - m))
          where
              m = randomRIO (0, sum)
Failed, modules loaded: none.

这几乎可以准确地告诉您出了什么问题-即m具有类型IO Int而不是Int

于 2012-11-02T09:15:20.213 回答
5

正如其他人指出的那样，您的算法不会给出均匀分布的输出。

获得统一输出的一种简单方法是：

  • 生成从到（含）n-1范围内的随机数0sum
  • 在随机数列表中插入0和sum
  • 对结果列表进行排序
  • 返回排序列表中连续值之间的差异列表

例子：

  • 假设我们想要四个总和为 100 的整数，我们从 RNG 请求三个随机值，它给了我们[72,33,43]
  • 我们插入0和100排序列表，给出[0,33,43,72,100]
  • 我们计算差异[33-0, 43-33, 72-43, 100-72]
  • 结果将是[33,10,29,28]

在哈斯克尔：

randomsWithSum :: (Num n, Ord n, Random n) => Int -> n -> IO [n]
randomsWithSum len sum =
    do b <- sequence $ take (len-1) $ repeat $ randomRIO (0,sum)
       let sb = sort (sum:b) in
           return $ zipWith (-) sb (0:sb)

对于您的示例，您可以将其称为randomsWithSum 26 (301::Int)

这同样适用于浮点类型，例如randomsWithSum 4 (1::Double)

编辑交换了参数，因此26 `randomsWithSum` 301正如其名称所暗示的那样。

于 2012-11-02T17:52:42.437 回答
0

根据 demas 的评论，我试图调整你的算法。我们可能希望每个n数字都与所有其他数字“相同”，因此我们将尝试直到得到正确的总和。也许有更好的方法。

-- f 0 rng = return []
-- f n rng = randomRIO (0,rng) >>= (\x-> fmap (x:) $ f (n-1) rng)

g n sumval = 
  let s = 2*sumval `div` n  -- expected value upto z is probably z/2,
      h i = do              --              if all are equally likely
              xs <- sequence $ replicate n (randomRIO (0,s))
              if sum xs == sumval 
                then return (xs, i)       -- i is number of attempts
                else h (i+1)
  in h 1

-- test:
Prelude System.Random> g 26 301
([15,23,15,0,13,8,23,11,13,19,5,2,10,19,4,8,3,9,19,16,8,16,18,4,20,0],2)
Prelude System.Random> g 26 301
([20,14,3,6,15,21,7,9,2,23,22,13,2,0,22,9,4,1,15,10,20,7,18,1,18,19],12)
Prelude System.Random> g 26 301
([4,3,4,14,10,16,20,11,19,15,23,18,10,18,12,7,3,8,4,9,11,5,17,4,20,16],44)
Prelude System.Random> g 26 301
([6,6,22,1,5,14,15,21,12,2,4,20,4,9,9,9,23,10,17,19,22,0,10,14,6,21],34)
Prelude System.Random> g 26 301
([20,9,3,1,17,22,10,14,16,16,18,13,15,7,6,3,2,23,13,13,17,18,2,2,8,13],169)
于 2012-11-02T11:06:08.173 回答