[Haskell-beginners] sorting almost sorted list

[Yitzchak Gale]

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