Arrays

Like many languages, Haskell has an array type for a fixed size group of elements. Haskell's arrays are a bit different than other languages for a few reasons, as we'll explore!

For more in depth examples, including practice problems with arrays and other structures, take a look at our Data Structures In-Depth eBook!

What are Arrays good for?

Arrays are great when you have data that is associated with some kind of numerical index and you would like to quickly access the data for arbitrary indices. Whereas other associative data structures have logarithmic access, arrays allow for truly constant time (O(1)) access. They also store their data more efficiently in memory.

What are Arrays not as good for?

While array implementations in most (mutable) languages allow for constant time modifications to values in the array, this does not work with the basic Haskell array type. As we'll discuss, the modification function must create an entirely new array. So this type works best with data that can be preprocessed and referenced repeatedly throughout an algorithm.

There are other types of arrays Haskell (mutable arrays, diff arrays) that fix this shortcoming, at the price of introducing IO computations to your program. We'll focus on the normal immutable array here.

Array Parameters and Constraints

Arrays are like maps in that they have two parameters. Instead of calling these "key" and "value" though, we usually say "index" and "element". There are no constraints on the "element" type, but the "index" type must satisfy the special Ix typeclass for indexing. This class ensures you can create an unbroken, discrete range from any two values of this type. You'll mainly use Int or some other Integral type. Enum-erated types also work, though they're less common. And as we'll discuss below, any tuple of indexable types is also indexable.

How do I create an Array?

Arrays are initialized a bit differently from the other types we've seen so far. There are two principal functions:

array :: (Ix i) => (i, i) -> [(i, e)] -> Array i e
listArray :: (Ix i) => (i, i) -> [e] -> Array i e

Both of these require you to supply a tuple with the minimum and maximum index of the array. Most languages require all arrays to start with index 0 and go until the number of elements (minus 1). In Haskell, your arrays can start and end with whatever index you choose.

You'll also need to supply the initial elements of your array. With the array function, you explicitly assign an index to each element in a tuple, similar to Map.fromList. With listArray, you simply provide the list of elements, and it will match them with indices in the order they appear.

Since arrays can be a bit more confusing, we'll keep track of a couple examples as we go along. We'll use these array definitions below.

>> let array1 = array (0, 3) [(1, 5), (0, 4), (2, 6), (3, 7)]
>> let array2 = listArray (4, 8) [2, 4, 6, 8, 10]

You should take care to make sure that the list of elements you provide matches the expected range of the indices.

How do I get the size of an Array?

Arrays do not have an explicit size function like our preceding types, but there are two approaches here. Because they implement the Foldable class, arrays can use the length function from Data.Foldable. However, this general implementation takes O(n) time.

Thus, it's also useful to know about the bounds function, which can determine the size more quickly. This will return a tuple of the minimum and maximum bounds of the array. You can then use the rangeSize function from Data.Ix to determine the size of the array.

>> import qualified Data.Foldable as F
>> import qualified Data.Ix as Ix
>> F.length array1
4
>> bounds array2
(4, 8)
>> Ix.rangeSize . bounds $ array2
5

Can I add items to an Array?

Unlike our previous types, you cannot efficiently "add" or modify the elements of a basic array. The general use case is that you initialize the array with all its elements. You can, however, create a new array with certain modifications by using the (//) operator.

(//) :: Array i e -> [(i, e)] -> Array i e

The first argument is the original array. The second argument is an association list of the changes you want to make, with the indices and new values paired together. The result is a new array that is identical to the original except for the changes.

>> let array3 = array1 // [(1, 15), (2, 16)]

Note that the old values of the array are all copied, so this is an O(n) operation.

How do I access Array elements?

The core function for accessing elements in an array is the bang operator (!). Given the array and the index, this will produce the value:

(!) :: Array i e -> i -> e
...
>> array1 ! 0
4
>> array1 ! 1
5
>> array2 ! 7
8
>> array3 ! 1
15

As with the same operator with maps, if the index does not exist, this will throw an error. However, with arrays, there is no comparable lookup function returning a Maybe value. You should generally know the bounds of the array you are working with before you access it. If you don't know, you can always use the bounds function from above.

If you need "all" the items in your array, you can get all the elements, all the indices, or both paired together (the associations) with these functions:

elems :: Array i e -> [e]
indices :: Array i e -> [i]
assocs :: Array i e -> [(i, e)]

...
>> indices array1
[0, 1, 2, 3]
>> elems array1
[4, 5, 6, 7]
>> assocs array1
[(0, 4), (1, 5), (2, 6), (3, 7)]

Can I delete items from an Array?

Arrays do not support "removing" elements, as their size must remain fixed by the indices. So the only "removal" you could do would really be a modification using (//) from above.

Can I combine Arrays?

There are no built-in functions for combining two arrays. Any kind of combination would require some kind of constraints on the size/dimensions of the inputs, and this is not something Haskell library functions naturally support.

Import Notes

As usual, we qualify most of our imports except the type name and the operators.

import Data.Array (Array, (//), (!))
import qualified Data.Array as A

Conclusion

If you want to learn about more data structures in Haskell, make sure to head back to the series page! If you'd like to keep following our series order, you can read about Vectors next!