# [Haskell-cafe] Linear shuffle

Daniel Fischer daniel.is.fischer at web.de
Fri Jan 14 07:46:27 EST 2005

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