Haskell High Performance Programming

Handling tabular data

If you need O(1) general indexing, a table-like data structure is virtually your only option. The Haskell report specifies the array package, which provides tables indexed by anything with an instance for a Ix typeclass.

Immutable arrays come in two flavors (we'll discuss mutable arrays later):

• Data.Array.Array: Immutable arrays of boxed values
• Data.Array.Unboxed.UArray: Immutable arrays of unboxed values

A common use case for Immutable arrays is memoization. For example, a table of Fibonacci numbers could be constructed as follows:

-- file: fib-array-mem.hs
import Data.Array

fib :: Int -> Array Int Integer
fib n = arr where
  arr = listArray (1,n) $ 1 : 1 : [ arr!(i-2) + arr!(i-1)| i <- [3..n] ]

We can also index by a tuple, which ...