[Haskell-cafe] Linear shuffle

[Ketil Malde]

Gracjan Polak <gracjan at acchsh.com> 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.  Then, given the index
'r' you could use 'splitAt r' to split the string, and join the first
part to the tail of the second, prepending the head of the second.
More precisely (I hope this is not a homework excercise :-):

     :
     (s1,s2) = splitAt r 
     return (head s2 : s1 ++ tail s2)

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

-kzm
-- 
If I haven't seen further, it is by standing in the footprints of giants