[Haskell-cafe] Strange random choice algorithm

[Hans Aberg]

On 30 Jan 2010, at 20:59, michael rice wrote:

> I'm not sure where I got this PICK function from, and don't  
> understand why it's written as it is, so I wanted to test it for  
> randomness. It seems random enough. But if I understand the  
> algorithm correctly, instead of selecting one of the elements from  
> the list, it eliminates all the elements but one and that's the  
> value it returns. Seems like a roundabout way of doing it. Comments?

Below is a function draw() that shuffles an interval, and prints it out.

   Hans

----
import Random

getRandomIndex :: [a] -> IO(Int)
getRandomIndex ls = getStdRandom(randomR(0, (length ls) - 1))

remove                :: Int -> [a] -> [a]
remove 0 (x:xs)       = xs
remove n (x:xs) | n>0 = x: remove (n-1) xs
remove _ (_:_)        = error "remove: negative argument"
remove _ []           = error "remove: too large argument"

shuffle :: [a] -> IO [a]
shuffle [] = return []
shuffle ls = do i <- getRandomIndex ls
                 do l <- shuffle (remove i ls)
                    return ((ls !! i) : l)

draw ls = do k <- shuffle ls
              putStr (show k)
----