In today’s Programming Praxis exercise we have to implement two algorithms that select random items from a list in linear time. Let’s get started, shall we?
Some imports:
import Control.Monad import Data.List import System.Random
I found myself doing the same thing in both functions so I factored it out. This function gives you an x in y chance of choosing a instead of b.
chance :: Int -> Int -> a -> a -> IO a chance x y a b = fmap (\r -> if r < x then a else b) $ randomRIO (0, y - 1)
The first algorithm (selecting one item at random from a list) can be done by folding over the list, with each item having a decreasing chance of becoming the new choice.
fortune :: [a] -> IO a fortune = foldM (\a (n, x) -> chance 1 n x a) undefined . zip [1..]
The second algorithm (selecting m items from a list of integers) is pretty much the same, except now we also have to keep track of how many items we selected. This version always goes through the entire list rather than stopping when m items have been selected, but since it still runs in O(n) and the resulting code is cleaner I went with this version.
sample :: Int -> Int -> IO [Int] sample m n = fmap snd $ foldM (\(m', a) x -> chance m' x (m' - 1, x:a) (m', a)) (m, []) [n, n-1..1]
With random algorithms it’s always a good idea to check the distribution of the results, as was proven again today because it revealed a bug in my code.
main :: IO () main = do let dist n f = mapM_ (\x -> print (length x, head x)) . group . sort . concat =<< replicateM n f dist 10000 . fmap return $ fortune ["rock", "paper", "scissors"] dist 10000 $ sample 6 43
The frequency distribution is pretty much equal and they sum up to the correct amount, so everything seems to be working correctly.
Tags: bonsai, code, Haskell, kata, praxis, programming, random, selection
December 10, 2010 at 2:41 pm |
Please tell us about the bug.
December 10, 2010 at 3:30 pm |
As usual, the code went through several iterations, so I can’t recall the exact code that produced the bug, but the basic problem was that by using ints instead of floats for the random number generation I introduced an off-by-one error because the bounds of randomRIO are inclusive, which means that asking for, say, 6 samples often produced only 4 or 5 because the final odds were 1 in 2 instead of 1 in 1.
April 5, 2011 at 11:35 am |
[...] we wrote some code in a previous exercise to select a random item from a list we can just use that here [...]