[Haskell-cafe] Quadratic complexity though use of STArrays

[Daniel Fischer]

Am Dienstag 22 September 2009 22:31:48 schrieb Daniel Fischer:
> That doesn't explain the quadratic behaviour of shuffleArr, though.
> I suspect it's laziness, things aren't actually done until the result is
> finally demanded, but I would have to take a closer look to really find
> out.

Yep. Strictifying things gives the expected linear behaviour.

In
    swap a n m = do
        [n',m'] <- mapM (readArray a) [n,m]
        mapM (uncurry $ writeArray a) [(m,n'),(n,m')]

you don't actually read and write values, but ever longer thunks.

Changing swap to

    swap a m n
        vm <- readArray a m
        vn <- readArray a n
        writeArray a n $! vm
        writeArray a m $! vn

is all you need to do (as long as your values have a simple type).