This is the Haskell version of my recursive Fisher-Yates shuffle in JS.
import System.Random pick :: Int -> [a] -> ([a],[a]) pick _  = (,) pick 0 (x:xs) = ([x],xs) pick i (x:xs) = (,) <$> fst <*> ((x:) . snd) $ pick (i-1) xs shuffle :: [a] -> IO [a] shuffle = runner =<< length where runner :: Int -> [a] -> IO [a] runner 0 xs = return xs runner i xs = randomRIO (0, i-1) >>= \r -> let (y,ys) = pick r xs in (y ++) <$> runner (i-1) ys
pick function fetches the
i'th item in a the list as a singular list alongside a list with the remaining items. ie
pick 3 [1,2,3,4,5,6,7] = (,[1,2,3,5,6,7]).
Although the above code is a version of the modern method which is claimed to work in O(n) this pretty fast shuffle code still seems to work in exponential time (i think).
Prelude Main> take 10 <$> shuffle [1..100000] [20141,12487,79977,44600,14825,86744,65941,84737,97850,21214] (0.57 secs, 334,790,152 bytes) Prelude Main> take 10 <$> shuffle [1..1000000] [698377,452503,263121,737622,550957,927399,453318,657374,728367,775039] (6.81 secs, 3,782,234,776 bytes)
I have two questions.
- Can the time complexity improved while using the List type?
- I am not fully in control of Haskell's performance gimmicks like unboxed types and such. Can it's performance boosted by means of such Haskell tools or what data type would be the best?