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 valuesData.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 gives the array extra dimensions. The symmetric Pascal matrix will serve as an example:
pascal :: Int -> Array (Int, Int) Integer
pascal n = arr where
arr = array ((1,1),(n,n)) $
[ ((i,1),1) | i <- [1..n] ] ++
[ ((1,j),1)...