But speed is another issue -- the list based version is a lot faster. Okay, I use UArrays and permute them by (//), and this operation is totally dominant in the profile. Is it correct that GHC is very naive about updating them, and even small updates cost O(n)? Is it better to (//) over few large lists than over many small ones?
Yes, (//) is terrible. It *never* tries to update in-place. Pretty much, haskell arrays (the non state ones) are very good datastructures for algorithms in which you initialize them and then read from them, but never overwrite. If you need to overwrite, you're almost always better off with a more functional datastructure like Data.FiniteMap (or Lists), or using either IOUArray or STUArray. DiffArrays are very flaky and I would recommend staying away from them, since sometimes (someone more experienced with them can comment more on them) they behave very unexpectedly (with respect to creating new versions of themselves). - Hal