I want to generate a list with 26 random integers which sum is 301 with Haskell. I write the following:
import System.Random
f 1 sum = [sum]
f n sum = m : (f (n-1) (sum-m))
where m = randomRIO (0,sum)
but it can't be compiled! I am confused with 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)
The error message is somewhat confusing in this case, but the punchline is that you need to work in the IO monad, since it's using randomRIO which is in IO, and there is (by design) no way to run IO code from non-IO code.
f 1 sum = return [sum]
f n sum = do
x <- randomRIO (0, sum)
xs <- f (n - 1) (sum - x)
return (x : xs)
As others have pointed out, your algorithm will not give uniformly-distributed output.
An easy way to get uniform output is:
- Generate
n-1 random numbers in the range from 0 to sum (inclusive)
- Insert
0 and sum into the list of random numbers
- Sort the resulting list
- Return the list of differences between consecutive values in the sorted list
Example:
- Suppose we want four integers with a sum of 100, we request three random values from the RNG and it gives us
[72,33,43]
- We insert
0 and 100 and sort the list, giving [0,33,43,72,100]
- We compute the differences
[33-0, 43-33, 72-43, 100-72]
- The result would be
[33,10,29,28]
In 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)
For your example you would call this as randomsWithSum 26 (301::Int)
The same applies to floating-point types, e.g. randomsWithSum 4 (1::Double)
Edit Swapped the arguments, so that 26 `randomsWithSum` 301 does what its name suggests.
As an aside to what hammer wrote, the error message becomes a lot more clear if you write the type you expect for the f function:
f :: Int -> Int -> [Int]
f 1 sum = [sum]
f n sum = m : (f (n-1) (sum-m))
where m = randomRIO (0,sum)
gives the error:
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.
Which pretty much tells you exactly what is wrong - that is m has type IO Int rather than Int
Following the comment by demas, I tried to tweak your algorithm. We probably want each of the n numbers be "the same" as all the others, so we'll just try until we get the correct sum. Maybe there is a better way.
-- 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)
