Haskell随机数无法构建无限类型：a1 = IO a1。

Question

Haskell随机数无法构建无限类型：a1 = IO a1。

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)

- speeding

2

你已经得到了有关Haskell的答案，但我认为该算法不是生成随机数的理想选择。例如，'f 20 100'返回[85,14,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]。你会得到一个很长的零尾巴作为此算法的结果。作为第一种方法，我将尝试选择另一种策略-将您的总和按随机比例分割。例如，f 5 100-将100随机分成两部分（例如30和70），并为每个数字调用f函数。 - ceth

4个回答

5

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

一个简单的方法来获得均匀的输出是：

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

例如:

假设我们希望得到四个和为100的整数，我们从随机数生成器请求三个随机值，并得到 [72,33,43]
我们将 0 和 100 插入随机数列表并排序，得到 [0,33,43,72,100]
计算这些数之间的差值：[33-0, 43-33, 72-43, 100-72]
结果是 [33,10,29,28]

Haskell 代码示例：

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做出其名称所示的操作。

- finnw

5

< p>除了 hammer 所写的之外，如果您在 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

- David Miani

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)

- Will Ness

这里有一个不同的问题：任何元素都不可能超过2*sumval `div` n。 - hammar

如果按照您的解释，解决方案很简单：只需在原始代码后调用“permutations”。每个这样的列表是否同等可能是一个单独的问题。也许问题在于元素范围的规定不足。 - Will Ness

1

是的，我知道你想做什么，但要获得均匀分布比那更难。只是在原始代码之后洗牌列表也不行，它仍然会偏向大部分为零的列表。 - hammar

1

@hammar 对，我的算法不会有这个问题。而且，由于该问题在个别范围方面未明确说明，我认为这是一个有效的答案。 - Will Ness

1

有更好的方法，但这不是它。请参见https://dev59.com/flbTa4cB1Zd3GeqP7hqu。 - finnw

显示剩余4条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hammar · Accepted Answer

在这种情况下，错误信息有点令人困惑，但关键是您需要在 IO monad 中工作，因为它使用的是 randomRIO，而该函数位于 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)