Re: [Haskell-beginners] sorting almost sorted list

Sorry to keep replying to myself here. I wrote:

Here is the more randomized test data:

I forgot one function: randomRS = state . randomR "state" and "evalState" are from Control.Monad.Trans.State.

test n k = fmap (all isSorted . map (sortAlmostBy n compare)) $ rands2 k

isSorted xs = and . zipWith (<=) xs $ drop 1 xs

rands1 d = do    cs <- replicateM (2000 `div` d) $ randomRS (0, d-1)    fmap concat $ zipWithM mkChunk (scanl (+) 0 cs) cs  where    mkChunk x y = replicateM y $ randomRS (x, x+y-1)

rands2 d = fmap (evalState . replicateM 100 $ rands1 d) newStdGen