Building Arrays and Reading Array Elements
To construct an array, we need to provide the list of elements we want to store in the array. This comes in two flavours.
array
First, there's the array function:
array :: Ix i => (i, i) -> [(i, e)] -> Array i e
To use any of the array-related types and functions, you need to import the
Data.Array module. Since arrays aren't used nearly as widely as lists in
Haskell code, the various array functions are not part of the Prelude.
The type signature of array says that to construct an array of type
Array i e, that is, indexed by values of type i and storing elements of type
e, we need i to be an instance of the Ix type class; i needs to be a
valid index type.
As the first argument to array, we need a pair of type (i, i). This is the
range of valid array indices. For example, we can construct an array that
accepts character indices between 'b' and 't'. Its index range would be
('b', 't'). Or we may construct a "2-dimensional" array that is indexed by
integer pairs, where the index in the first dimension can range from 1 to 10 and
the index in the second dimension can range from 32 to 43. In that case, i is
the type (Int, Int), and the index range given to array as the first
argument is ((1, 32), (10, 43)). The lowest possible index of an array entry
is (1, 32). The maximum index is (10, 43). We can also build array indices
that are tuples whose components are different types. For example, we could use
(Bool, Int) as the index type of a 2-d array whose first dimension is indexed
by Bool and whose second dimension is indexed by Int. An array allowing
indices between (False, 1) and (True, 10) would have index range
((False, 1), (True, 10)).
The second argument of array is a list of pairs of type (i,e). For each pair
in this list, the second component, of type e, is an element to be stored in
the array, and the first component, of type i, indicates the array cell where
this element is to be stored. For example, here is an array of size 3 that
stores the character 'a' at position 1, the character 'd' at position 2, and the
character 'x' at position 3:
>>> arr = array (1,3) [(3,'x'),(1,'a'),(2,'d')]
As this example demonstrates, the pairs in the list do not need to be arranged in a particular order. To read array entries, we have the indexing operator
(!) :: Ix i => Array i e -> i -> e
It takes the array to be accessed and an index as argument, and it returns the element stored at the given index:
>>> arr!1
'a'
>>> arr!2
'd'
>>> arr!3
'x'
>>> arr!0
*** Exception: Ix{Integer}.index: Index (0) out of range ((1,3))
This shows that the elements at indices 1, 2, and 3 in the array we constructed earlier are indeed the claimed characters. The last example shows that if we try to access an array index that does not exist, our program panics.
You may wonder what happens when the list of pairs used to populate the array contains multiple pairs with the same index. For example, the following list contains the index 1 twice:
>>> arr = array (1,3) [(3,'x'),(1,'a'),(2,'d'),(1,'z')]
In this case, it is the last list entry with a given index that overwrites all
entries with the same index earlier in the list. So, our new array arr stores
'z' in the first array slot:
>>> arr!1
'z'
listArray
The second function we have to build arrays is
listArray :: Ix i => (i, i) => [e] -> Array i e
The first argument is exactly the same as for array, but instead of a list of
index-element pairs, the second argument is simply a list of elements. The array
gets populated with the elements in this list in order of increasing indices.
For example,
>>> arr = listArray (1,26) ['A'..'Z']
>>> arr!1
'A'
>>> arr!26
'Z'
If the list provided has more elements than there are array slots, the extra
list entries are ignored. If the list has fewer elements than there are array
slots, then the array slots for which we don't have elements are left
undefined:
>>> arr = listArray (1,3) ['a']
>>> arr!1
'a'
>>> arr!2
*** Exception: (Array.!): undefined array element
Exercise
I said that listArray populates the array with the elements in the list in
order of increasing indices. What might this look like for 2-d arrays or
higher-dimensional arrays?
Construct two arrays using
listArray ((1,1), (3,3)) ['a'..]
and
listArray ((1,1,1), (2,2,2)) ['a'..]
Try to explain in words what "increasing indices" means when the indices aren't integers or characters but pairs or tuples of values.
Solution
When using tuples as array indices, Haskell arrays use what is often
described as row-major order. For 2-d arrays, we usually think about
an index \((i,j)\) as referring to the entry in row \(i\) and column \(j\).
Row-major order means that in memory, the array elements are arranged in
order of increasing rows and, within each row, in order of increasing
columns. Thus, for a 2-d array with index range ((1,1), (3,3)), the
array slots are arranged in the order
(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3). This is
exactly the order in which listArray populates these slots:
>>> listArray ((1,1),(3,3)) ['a'..]
array ((1,1),(3,3)) [((1,1),'a'),((1,2),'b'),((1,3),'c'),
((2,1),'d'),((2,2),'e'),((2,3),'f'),((3,1),'g'),((3,2),'h'),
((3,3),'i')]
For higher-dimensional arrays, the intuition of rows and columns fails a
little, but the idea is the same. We lay out the array elements in order
of increasing first dimension. The elements with the same index in the
first dimension are laid out in order of increasing second dimension.
The elements with the same indices in both the first and second
dimension are laid out in order increasing third dimension. And so on.
Thus, for a 3-d array with index range ((1,1,1), (2,2,2)), the array
slots are arranged in the order
(1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2).
This is exactly the order in which `listArray populates these slots:
>>> listArray ((1,1,1),(2,2,2)) ['a'..]
array ((1,1,1),(2,2,2)) [((1,1,1),'a'),((1,1,2),'b'),((1,2,1),'c'),
((1,2,2),'d'),((2,1,1),'e'),((2,1,2),'f'),((2,2,1),'g'),((2,2,2),'h')]