Re: [Haskell-cafe] Linear shuffle

Am Freitag, 14. Januar 2005 09:50 schrieb Ketil Malde:

Gracjan Polak writes:

...

shuffle :: [a] -> IO [a] shuffle [] = return [] shuffle x = do r <- randomRIO (0::Int,length x - 1) s <- shuffle (take r x ++ drop (r+1) x) return ((x!!r) : s)

This algorithm seems not effective, length, take, drop and (!!) are costly. Is there any better way to implement shuffle?

The length seems to me to be constant, so you could presumably calculate it once, and pass it as a parameter.

Whether the length is constant depends on how you interpret this statement, passing it as a parameter is absolutely the thing to do, say shuffle :: [a] -> IO [a] shuffle as = do let len = length as lenShuffle as len lenShuffle :: [a] -> Int -> IO [a] lenShuffle _ 0 = return [] lenShuffle as n = do r <- randomRIO (0,n-1) let (xs, h:ys) = splitAt r as s <- lenShuffle (xs++ys) (n-1) return (h:s)

This reduces the three (four if you include length) traversals to one.

and apparently is of linear behaviour. BTW, if splitAt were implemented as stated in the report, it wouldn't be any better than using take and drop, even as is, it saves only about 25% of the work. The real villains in the original code are the repeated evaluation of length and (!!), both leading to O(n^2) complexity (I think, I didn't properly analyze it).

-kzm all the best, Daniel