[Haskell-cafe] Re: Random question
lemming at henning-thielemann.de
Sun Oct 5 14:06:03 EDT 2008
On Sun, 5 Oct 2008, Iain Barnett wrote:
> I just wanted to say thanks to everyone that helped me on this. I'm still
> reading/cogitating the stuff you gave me, but I did manage to write a
> Fisher-Yates shuffle using random numbers. I had a lightbulb moment while
> reading about sequence (so I suppose that might count as my 7th Monad
> tutorial :). The <- takes values out of monads. So simple!
> -- let c = [11..18] --shuff (length c) c
> shuff :: Int -> [a] -> IO [a]
> shuff 0 xs = return xs
> shuff (len + 1) xs = (rand 1 (len + 1)) >>= \r -> shuff len $ requeue r xs
> where requeue = \z xs -> (init $ take z xs) ++ (drop z xs) ++ [last $ take z xs]
Instead of separate calls to 'take' and 'drop' you may prefer 'splitAt':
requeue z xs =
let (prefix,pivot:suffix) = splitAt (z-1) xs
in prefix ++ suffix ++ [pivot]
However, accessing list elements by index is pretty inefficient (linear
time with respect to index). Is it possible to re-arrange the algorithm?
Maybe using more efficient data structures?
More information about the Haskell-Cafe