How can I obtain constant time access (like in an array) in a data structure in Haskell?

Question

I'll get straight to it - is there a way to have a dynamically sized constant-time access data-structure in Haskell, much like an array in any other imperative language?

I'm sure there is a module somewhere that does this for us magically, but I'm hoping for a general explanation of how one would do this in a functional manner :)

As far as I'm aware, Map uses a binary tree representation so it has O(log(n)) access time, and lists of course have O(n) access time.

Additionally, if we made it so that it was immutable, it would be pure, right?

Any ideas how I could go about this (beyond something like Array = Array { one :: Int, two :: Int, three :: Int ...} in template Haskell or the like)?

Answer 1

If your key is isomorphic to Int then you can use IntMap as most of its operations are O(min(n,W)), where n is the number of elements and W is the number of bits in Int (usually 32 or 64), which means that as the collection gets large the cost of each individual operation converges to a constant.

Answer 2

a dynamically sized constant-time access data-structure in Haskell,

• Data.Array
• Data.Vector

etc etc.

For associative structures you can choose between:

• Log-N tree and trie structures
• Hash tables
• Mixed hash mapped tries

With various different log-complexities and constant factors.

All of these are on hackage.

Answer 3

In addition to the other good answers, it might be useful to say that:

When restricted to Algebraic Data Types and purity, all dynamically sized data structure must have at least logarithmic worst-case access time.

Personally, I like to call this the price of purity.

Haskell offers you three main ways around this:

• Change the problem: Use hashes or prefix trees.
• For constant-time reads use pure Arrays or the more recent Vectors; they are not ADTs and need compiler support / hidden IO inside. Constant-time writes are not possible since purity forbids the original data structure to be modified.
• For constant-time writes use the IO or ST monad, preferring ST when you can to avoid externally visible side effects. These monads are implemented in the compiler.