[Haskell-beginners] Complexity of Arrays in Haskell

[Isaac Dupree]

On 05/10/11 03:51, Øystein Kolsrud wrote:
> Hi! What's the complexity of indexing arrays in Haskell? The
> Data.Array documentation doesn't seem to mention complexity of any of
> its functions, and it's not obvious to me how to implement an array
> data structure with indexing being O(1).

Compilers implement special representation of arrays (an array in 
memory, rather as you might expect), so indexing is O(1).  The price you 
pay is that array *updates* are O(n) even if you're only changing one 
element.  It has to copy the whole thing in order to leave the original 
unmodified.

(There are also mutable arrays that are more annoyingly imperative to 
use, Data.Map which has good enough performance for a lot of purposes, etc.)