[Haskell-cafe] Linear shuffle

[Daniel Fischer]

Am Freitag, 14. Januar 2005 09:50 schrieb 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.  

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