[Haskell-cafe] Re: Random question

[Henning Thielemann]

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[1]. 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?