How fast is Data.Array?

Question

The Data.Array documentation says:

Haskell provides indexable arrays that can be thought of as functions whose domains are isomorphic to adjacent subsets of integers. Functions limited in this way can be implemented efficiently; in particular, a programmer can reasonably expect quick access to components.

I wonder how fast (!) And (//) can be. Can I expect O (1) complexity from them, as their true colleagues would have?

Answer 1

All in all, yes, you should expect O (1) from ! although I am not sure that this is guaranteed by the standard.

You might want to see a vector package if you need faster arrays (through the use of stream merging). It is also better designed.

Note that // is probably O (n), although due to the fact that it must cross the list (just like an urgent program). If you need a big mutation, you can use MArray or MVector .