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?
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
