randomwalker

import System.Random
import Ix

-- general notes:
--    1. is it really this painful to do anything with random numbers?
--    2. the RNG doesn't even work very well, seems to be linear-congruential
--       how do i get Mersenne Twister?

-- attempt 1: straightforward translation of standard idiom; quadratic time
permute1 xs = permute_ xs (mkStdGen 0) where
    permute_ [] rgen = []
    permute_ xs rgen = let (idx, newrgen) = randomR (1, length xs) rgen in
                       xs!!(idx-1) : permute_ (take (idx-1) xs ++ drop idx xs) newrgen

-- attempt 2: decorate-sort-undecorate
permute2 xs = permute_ xs (iteraternd (mkStdGen 0) random) where
    -- had to force input type to Int because
    -- i can't figure out what's the base class for sortable types
    permute_ :: [Int] -> [Int] -> [Int]
    permute_ xs rnds = map snd (qsort (zip rnds xs)) where
        -- why does 'sort' work in the prelude but not here?
        qsort [] = []
        qsort (x:xs) = qsort (filter (<=x) xs) ++ [x] ++ qsort (filter (>x) xs)
    -- i'm hoping this is somewhere in the library and i've missed it
    iteraternd g rnd = let (val, newg) = rnd g in val : iteraternd newg rnd

-- attempt 3: not really sure where i was going with this..
-- neither linear-time nor a perfect shuffle
-- strategy is to split in half, permute each, and merge 'randomly'
permute3 xs = permute_ xs (mkStdGen 0) where
    permute_ []  rgen = []
    permute_ [x] rgen = [x]
    permute_ xs  rgen =
        let mid = (length xs) `div` 2; (rgen1, rgen2) = split rgen in
        merge (permute_ (take mid xs) rgen1)
              (permute_ (drop mid xs) rgen2)
              []
              rgen
    -- acc is needed to make merge tail-recursive
    merge xs [] acc rgen = xs ++ acc
    merge [] ys acc rgen = ys ++ acc
    merge (x:xs) (y:ys) acc rgen =
        let (rnd, newrgen) = randomR (0,1) rgen :: (Int, StdGen) in
        if rnd == 0
            then merge xs ys (x:y:acc) newrgen
            else merge xs ys (y:x:acc) newrgen