[Haskell-beginners] Complexity of Arrays in Haskell

[Daniel Fischer]

On Tuesday 10 May 2011 09:51:21, Ø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).

For the array types provided by the array package (Array, UArray, STArray, 
STUArray, IOArray, IOUArray), indexing is O(1) [for reasonable index 
types¹].

Implementing such a data structure with O(1) indexing of course requires to 
go low-level, for the payload, you need a contiguous chunk of memory where 
either the pointers to the data are stored (boxed arrays) or the raw data 
themselves (unboxed arrays). Then indexing is "read size bytes from address 
(start + index*size)", just like in C or similar. Of course there's bounds-
checking and computing the effective index from the programmer-visible, but 
for reasonable index types, that is O(1) too.

¹ You could of course make an Ix instance for e.g. lazy Peano numbers, then 
indexing would become O(index).