Data Arrays

Another type that works kind of like a list but is more efficient for some operations is the array. Arrays are familiar from many other programming languages, but Haskell arrays are a bit different.

Unlike the Data.Map module, the Data.Array can just be imported normally:

import Data.Array

Now we can look at the type of the array function that constructs an array.

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

There are a couple of things to notice here. First of all, the Array type is parameterized by two types: the index type and the element type. Most other programming languages only parameterize arrays with the element type, but the index type is always int. In Haskell, we can have, for example, an Array Char Int: an array indexed by characters, or Array Bool String, an array indexed by booleans, or even Array (Int,Int) Int, a two-dimensional array of ints.

Not all types can be index types. Only types that are similar to integers are suitable. That is the reason for the Ix i class constraint. The Ix class collects all the types that can be used as array indices.

Secondly, the array function takes an extra (i,i) parameter. These are the minimum and maximum indices of the array. Unlike some other languages, where arrays always start at index 0 or 1, in Haskell you can define an array that starts from 7 and goes to 11. So here’s that array:

myArray :: Array Int String
myArray = array (7,11) [(7,"seven"), (8,"eight"), (9,"nine"), (10,"ten"), (11,"ELEVEN")]

Listing all the indices and elements in order can be a bit cumbersome, so there’s also the listArray constructor that just takes a list of elements in order:

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

myArray :: Array Int String
myArray = listArray (7,11) ["seven", "eight", "nine", "ten", "ELEVEN"]

Arrays are used with two new operators:

-- Array lookup
(!) :: Ix i => Array i e -> i -> e
-- Array update
(//) :: Ix i => Array i e -> [(i, e)] -> Array i e

Here’s an example GHCi session:

Prelude> import Data.Array
Prelude Data.Array> myArray = listArray (7,11) ["seven", "eight", "nine", "ten", "ELEVEN"]
Prelude Data.Array> myArray
array (7,11) [(7,"seven"),(8,"eight"),(9,"nine"),(10,"ten"),(11,"ELEVEN")]
Prelude Data.Array> myArray ! 8
"eight"
Prelude Data.Array> myArray // [(8,"ocho"),(9,"nueve")]
array (7,11) [(7,"seven"),(8,"ocho"),(9,"nueve"),(10,"ten"),(11,"ELEVEN")]

You might be wondering why the (//) operator does multiple updates at once. The reason is the main weakness of Haskell arrays: immutability. Since arrays can’t be changed in place, (//) must copy the whole array. This is why in Haskell it’s often preferable to use lists or maps to store data that needs to be updated. However, arrays may still be useful when constructed once and then used for a large number of lookups. We’ll get back to how Haskell data structures work in the next lecture.

Note! In this course we’ll use only Array, a simple array type that’s specified in the Haskell standard. There are many other array types like the mutable IOArray and the somewhat obscure DiffArray. There are also type classes for arrays like IArray and MArray. In addition to arrays there is a wide family of Vector types that can be more practical than Array for real programs.

Sidenote: Folding over Maps & Arrays

The Map and Array type are instances of Foldable just like lists are! This means you can use functions like length and foldr on them:

length (array (7,11) [(7,"seven"),(8,"eight"),(9,"nine"),(10,"ten"),(11,"ELEVEN")])
    ==> 5
foldr (+) 0 (Map.fromList [("banana",3),("egg",7)])
    ==> 10

Exercises

All exercises can be found in Set4a and Set4b. Please pay attention in the title of the exercise in which file the exercises of this section can be found.

Exercises from 4a:

You can check your current points from the blue blob in the bottom-right corner of the page.