How to get constant time access (e.g. in an array) in a data structure in Haskell?

Question

I'll go right away - is there a way to get a dynamically-sized data structure with constant access time in Haskell, like an array in any other imperative language?

I am sure that somewhere there is a module that does this for us magically, but I hope for a general explanation of how this can be done in functional mode :)

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

Besides, if we made it so that it is unchanged, it would be clean, right?

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

Answer 1

If your key is isomorphic to Int , you can use IntMap since 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 by as the collection grows, the cost of each individual operation converges to a constant.

Answer 2

dynamic data structure with constant access time in Haskell,

• Data.Array
• Data.Vector

etc.

For associative structures, you can choose between:

• Tree structure and log tree structure
• Hash tables
• Mixed hash attempts

With various different log-difficulties and constant factors.

All of them are hackers.

Answer 3

In addition to other good answers, it may be helpful to say that:

When restricting to Algebraic data types and purity, all dynamically sized data structures should have at least the logarithmic worst-case access time.

Personally, I like to call it the price of cleanliness.

Haskell offers you three main ways:

• Change the problem . Use hashes or prefix trees.
• For reading with constant time, use pure Arrays or later vectors ; they are not ADTs and require compiler / hidden I / O support inside. Time constant recording is not possible because cleanliness forbids changing the original data structure.
• To record in continuous recording mode, use the IO or ST monad, preferring ST , when you can avoid externally visible side effects. These monads are implemented in the compiler.