Take the 2-minute tour ×

I have accepted an answer to the question below, but It seemed I misunderstood how Arrays in haskell worked. I thought they were just beefed up lists. Keep that in mind when reading the question below.

I've found that monolithic arrays in haskell are quite inefficient when using them for larger arrays.

I haven't been able to find a non-monolithic implementation of arrays in haskell. What I need is O(1) time look up on a multidimensional array.

Is there an implementation of of arrays that supports this?

EDIT: I seem to have misunderstood the term monolithic. The problem is that it seems like the arrays in haskell treats an array like a list. I might be wrong though.

EDIT2: Short example of inefficient code:

fibArray n = a where
  bnds = (0,n)
  a = array bnds [ (i, f i) | i <- range bnds ]
  f 0 = 0
  f 1 = 1
  f i = a!(i-1) + a!(i-2)

this is an array of length n+1 where the i'th field holds the i'th fibonacci number. But since arrays in haskell has O(n) time lookup, it takes O(n²) time to compute.

share|improve this question
What do you mean by monolithic array? –  luqui Apr 19 '12 at 10:38
IO(U)Array and ST(U)Array do not look that monolithic... –  n.m. Apr 19 '12 at 10:56
Can you give a short example of inefficient code, so that we can zero in on the terminology? –  n.m. Apr 19 '12 at 11:03
The type [a] is a singly linked list; types like Data.Array.Array are closer to actual arrays. –  dbaupp Apr 19 '12 at 11:04
vector has O(1) indexing. –  Cat Plus Plus Apr 19 '12 at 11:08
add comment

3 Answers

up vote 4 down vote accepted

Arrays have O(1) indexing. The problem is that each element is calculated lazily. So this is what happens when you run this in ghci:

*Main> :set +s
*Main> let t = 100000
(0.00 secs, 556576 bytes)
*Main> let a = fibArray t
(0.01 secs, 1033640 bytes)
*Main> a!t  -- result omitted
(1.51 secs, 570473504 bytes)
*Main> a!t  -- result omitted
(0.17 secs, 17954296 bytes)

Note that lookup is very fast, after it's already been looked up once. The array function creates an array of pointers to thunks that will eventually be calculated to produce a value. The first time you evaluate a value, you pay this cost. Here are a first few expansions of the thunk for evaluating a!t:

a!t -> a!(t-1)+a!(t-2)-> a!(t-2)+a!(t-3)+a!(t-2) -> a!(t-3)+a!(t-4)+a!(t-3)+a!(t-2)

It's not the cost of the calculations per se that's expensive, rather it's the need to create and traverse this very large thunk.

I tried strictifying the values in the list passed to array, but that seemed to result in an endless loop.

One common way around this is to use a mutable array, such as an STArray. The elements can be updated as they're available during the array creation, and the end result is frozen and returned. In the vector package, the create and constructN functions provide easy ways to do this.

-- constructN :: Unbox a => Int -> (Vector a -> a) -> Vector a

import qualified Data.Vector.Unboxed as V
import Data.Int

fibVec :: Int -> V.Vector Int64
fibVec n = V.constructN (n+1) c
  c v | V.length v == 0 = 0 
  c v | V.length v == 1 = 1 
  c v | V.length v == 2 = 1
  c v = let len = V.length v
        in v V.! (len-1) + v V.! (len-2)

BUT, the fibVec function only works with unboxed vectors. Regular vectors (and arrays) aren't strict enough, leading back to the same problem you've already found. And unfortunately there isn't an Unboxed instance for Integer, so if you need unbounded integer types (this fibVec has already overflowed in this test) you're stuck with creating a mutable array in IO or ST to enable the necessary strictness.

share|improve this answer
we can add strictness in a gradual manner with controlled granularity k on the array arr which is recursively defined as in the Q, by threading seq through the array's elements, with foldl1 (\a b-> a seq` arr!b) [u,u+k..m] where (u,v)=bounds arr`, to access the m-th element of arr. –  Will Ness Apr 20 '12 at 8:23
@WillNess I don't generally like having to traverse a data structure a second time just to force elements, but it might be the most pragmatic solution in this case. –  John L Apr 20 '12 at 8:32
and, the thunk created at a!i is very small. It just says \()->f i. So when it's forced, the recursive function f is evaluated. There are no large thunks here, just deep recursion. Your expansion example is wrong: after a!(t-1) is polled, a!(t-2) just fetches the already calculated result from the array. –  Will Ness Apr 20 '12 at 8:36
"traversing"... it is traversed whether we like it or not, according to f's definition. We just make it be traversed from the bottom up, limiting recursion depth in each small step - instead of by one giant step which causes a very deep recursion, when demanding its top value right away. –  Will Ness Apr 20 '12 at 8:39
@WillNess - I said I don't like making a second traversal that's unnecessary. It doesn't matter if it's implicit (the OP) or explicit (your example), either way, a smarter construction algorithm would avoid it. –  John L Apr 20 '12 at 10:29
show 2 more comments

You're confusing linked lists in Haskell with arrays.

Linked lists are the data types that use the following syntax:


defined as:


These are classical recursive data types, supporting O(n) indexing and O(1) prepend.

If you're looking for multidimensional data with O(1) lookup, instead you should use a true array or matrix data structure. Good candidates are:

  • Repa - fast, parallel, multidimensional arrays -- (Tutorial)
  • Vector - An efficient implementation of Int-indexed arrays (both mutable and immutable), with a powerful loop optimisation framework . (Tutorial)
  • HMatrix - Purely functional interface to basic linear algebra and other numerical computations, internally implemented using GSL, BLAS and LAPACK.
share|improve this answer
So arrays from Data.Array are not just beefed up lists? –  Undreren Apr 19 '12 at 12:25
They are not lists. They are contiguous blocks of memory holding either pointers (Data.Array) or primitive values (Data.Array.Unboxed) –  Don Stewart Apr 19 '12 at 12:27
According to the most recent edit, I don't believe the OP is confusing linked lists with arrays. I believe it's a strictness problem, which may or may not be easily fixable, depending on the types involved. –  John L Apr 19 '12 at 14:58
add comment

Referring specifically to your fibArray example, try this and see if it speeds things up a bit:

-- gradually calculate m-th item in steps of k
--     to prevent STACK OVERFLOW , etc
gradualth m k arr                         
    | m <= v = pre `seq` arr!m   
    pre = foldl1 (\a b-> a `seq` arr!b) [u,u+k..m]
    (u,v) = bounds arr 

For me, for let a=fibArray 50000, gradualth 50000 10 aran at 0.65 run time of just calling a!50000 right away.

share|improve this answer
So, basically, you are just producing larger chunks? I tried to read the definition for seq, but it just said "Evaluates its first argument to head normal form, and then returns its second argument as the result." What does that mean? –  Undreren Apr 20 '12 at 6:06
It seems like seq a b calculates a, throws the result away, and then just return b. Is this what happens? –  Undreren Apr 20 '12 at 6:15
not larger thunks, on the contrary - smaller chunks. seq a b records the forcing dependency: when (if) b is forced, a is forced first, then b is forced, then b's value is returned. Forcing happens when a value is needed for pattern match, as much as needed for pattern match 2proceed. Here the effect is, as if you've evaluated a!10 first, then a!20, then a!30, all the way to your array's upper bound. So when a!n is polled, it finds a!(n-10) already pre-calculated, thus limiting the recursion depth to no more than 10. IOW this adds strictness, at controlled granularity. –  Will Ness Apr 20 '12 at 8:08
small correction: when seq a b is forced, a is forced first, then b is used in place of seq a b - which means, now b is forced. clarification: thus the very large thunk is broken into a series of smaller chunks of evaluation (thunks). –  Will Ness Apr 20 '12 at 8:11
That seems neat :) Thanks :) –  Undreren Apr 20 '12 at 9:34
add comment

Your Answer


