Building up a list in Haskell

Question

What I am wanting to do is create a list of random integers, with no duplicates. As a first step, I have a function which makes a list of n random samples. How does one write this in a more Haskell idiomatic way, where an empty list does not need to be passed in to start the list off? I am sure I am missing something basic and fundamental.

-- make a list of random integers.
-- takes a size, and an empty list.
-- returns a list of that length of random numbers.
f :: Int -> [Int] -> IO [Int]
f l xs | length xs >= l = return (xs)
f l xs = do
  r <- randomRIO (1, 40) :: IO Int
  f l $ r : x

Usage:

*Main> f 6 []
[10,27,33,35,31,28]

Ultimately this function will have filtering to check for duplicate insertions, but that is a separate question. Although this may look like homework, it is not, but part of my own attempt to come to grips with the State monad as used for random number generation, and finding I am stuck at a much earlier spot.

Can you do this with a wrapper function that hides the passing of the empty list? That seems possible, but very inelegant. — andro
– andro, Commented Sep 11, 2015 at 14:11

Bakuriu · Accepted Answer · 2015-09-11 14:19:39Z

3

Well, you can operate on the output of the recursive call:

f :: Int -> IO [Int]
f 0 = return []
f n = do
    r <- randomRIO (1, 40)
    xs <- f (n-1)
    return $ r : xs

Note however that it's important the the operation you perform on the result is fast. In this case r : xs is constant time. However if you replace the last line with (say):

    return $ xs ++ [r]

this would change the complexity of the function from linear to quadratic because every ++ call will have to scan all the sequence of previously generated numbers before appending the new one.

However you could simply do:

f n = sequence $ replicate n (randomRIO (1, 40))

replicate creates a [IO Int] list of length n made of randomRIO actions and sequence takes an [IO a] and turns it into an IO [a] by executing all the actions in order and collecting the results.

Even simpler, you could use replicateM which is already the function you want:

import Control.Monad(replicateM)

f n = replicateM n (randomRIO (1, 40))

or in point-free style:

f :: Int -> IO [Int]
f = flip replicateM $ randomRIO (1, 40)

edited Sep 11, 2015 at 14:19

answered Sep 11, 2015 at 14:13

Bakuriu

103k23 gold badges209 silver badges236 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

andro Over a year ago

Now, the next step is add check for duplicate insertion in the list (imagine a set of lottery numbers). With the elegant sequence and replicate code, I can't see how to get the added logic into the code.

Bakuriu Over a year ago

@andro Yes, you can't modify them to achieve that as well. However keep in mind that the fact that they limit what they can do is a good thing for correctness. When you have an explicit recursive definition it could do literally anything. Using special functions like folds or replicate etc. removes completely the chances of introducing many kinds of bugs. Moreover the compiler is able to apply optimization to such code while explicitly recursive code is a lot harder to optimize since compiler can't prove all properties they need for generic code.

kes · Accepted Answer · 2015-09-11 16:27:35Z

1

This uses a Set to keep track of numbers already generated:

import System.Random
import qualified Data.Set as Set

generateUniqueRandoms :: (Int, Int) -> Int -> IO [Int]
generateUniqueRandoms range@(low, high) n =
  let maxN = min (high - low) n
  in
     go maxN Set.empty

  where
     go 0 _ = return []
     go n s = do
        r <- getUniqueRandom s
        xs <- go (n-1) (Set.insert r s)
        return $ r : xs

     getUniqueRandom s = do
         r <- randomRIO range
         if (Set.member r s) then getUniqueRandom s
         else return r

Here is some sample output:

Main> generateUniqueRandoms (1, 40) 23
[29,22,2,17,5,8,24,27,10,16,6,3,14,37,25,34,30,28,7,31,15,20,36]

Main> generateUniqueRandoms (1, 40) 1000
[33,35,24,16,13,1,26,7,14,11,15,2,4,30,28,6,32,25,38,22,17,12,20,5,18,40,36,39,27,9,37,31,21,29,8,34,10,23,3]

Main> generateUniqueRandoms (1, 40) 0
[]

However, it is worth noting that if n is close to the width of the range, it'd be much more efficient to shuffle a list of all numbers in the range and take the first n of that.

edited Sep 11, 2015 at 16:27

answered Sep 11, 2015 at 15:17

kes

6,2778 gold badges46 silver badges71 bronze badges

1 Comment

andro Over a year ago

The set being passed here seems to me to represent state in the computation, a record of the past history. How would this be expressed with a State monad?

Collectives™ on Stack Overflow

Building up a list in Haskell

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related