Arrays and arrays

[Hal Daume III]

> 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