Arrays
An array has bounds
Data.Array is the middle ground between a list and a map: a block of elements in a fixed order, with an index range called the bounds. The type carries the index type and the element type, and the bounds live in the value:
listArray :: Ix i => (i, i) -> [e] -> Array i e
(!) :: Ix i => Array i e -> i -> e
bounds :: Array i e -> (i, i)
(//) :: Ix i => Array i e -> [(i, e)] -> Array i e
The index type needs Ix, which Int, Char, Bool and tuples of them satisfy. An array is immutable: // returns a new array with the listed positions replaced, and the old one stays valid, exactly like a map update.
listArray and the index operator
module Main (main) where
import Data.Array (Array, assocs, bounds, elems, indices, listArray, (!), (//))
table :: Array Int String
table = listArray (1, 4) ["alpha", "beta", "gamma", "delta"]
main :: IO ()
main = do
print (bounds table)
print (table ! 2)
print (elems table)
print (indices table)
print (assocs table)
print (table // [(2, "BETA")])
ghc -Wall -O1 -o table table.hs
./table
(1,4)
"beta"
["alpha","beta","gamma","delta"]
[1,2,3,4]
[(1,"alpha"),(2,"beta"),(3,"gamma"),(4,"delta")]
array (1,4) [(1,"alpha"),(2,"BETA"),(3,"gamma"),(4,"delta")]
(!) is a partial function at the type level: index 5 of this array is a run-time error, and the bounds are the only guard. The // update rebuilt the array with one position changed, and the Show instance prints array (1,4) [...]. Access is constant time because the elements are contiguous, which is the reason to reach for an array when the index is dense and known.
accumArray and a histogram
accumArray builds the array from a list of index and value pairs and combines the values that land on the same index. With (+) and a zero start it is a histogram:
module Main (main) where
import Data.Array (Array, accumArray, assocs, (!))
counts :: Array Char Int
counts = accumArray (+) 0 ('a', 'd') [('a', 1), ('c', 2), ('a', 3)]
main :: IO ()
main = do
print (assocs counts)
print (counts ! 'a')
print (counts ! 'b')
ghc -Wall -O1 -o counts counts.hs
./counts
[('a',4),('b',0),('c',2),('d',0)]
4
0
Every index in the bounds has an entry, including the letters with no occurrence, which is the difference from a map: 0 is a value and the printing shows it. The two a pairs were added by the combining function, and the input order did not matter because the index decided the position.
Arrays against lists and maps
- A list is best when the program walks the elements in order and never needs an index; indexing a list is linear.
- An array is best when the index is a dense range and the program looks elements up by position; access is constant and the bounds are checked by you.
- A map is best when the keys are sparse or not numeric; the cost is logarithmic and the type allows any Ord key.
The mutable counterpart is Data.Array.IO and Data.Array.ST, which live in array as well and are the reason the package exists: an in-place sort or a dynamic program needs to write cells in a loop. The immutable Array of this lesson is the value you hand to the rest of the program once the loop is done.
Exercises
- Build an array of the squares of 1 to 10 and print the fifth element.
- Use accumArray (*) and explain the result for an empty index.
- Write a function that returns the element at an index or a default, and compare it with (!).
- Compute the sum of an array with elems and with a fold.
- Explain why an array index is not checked at compile time and what a safer wrapper would look like.
- Build the same histogram with Data.Map and compare the printed forms.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does an array carry besides its elements?
Answer
Its bounds, the lowest and highest index
An Array i e is a pair of bounds and the elements in that range.
-
What does
table ! 2do?Answer
Returns the element at index 2
The (!) operator is the constant-time index lookup.
-
What happens at
table ! 5when the bounds are (1,4)?Answer
A run-time error
The index is checked against the bounds when it is used, and an out-of-range index is an error.
-
What does this program print?
module Main (main) where import Data.Array (listArray, (!)) main :: IO () main = print ((listArray (0, 2) [10, 20, 30 :: Int]) ! 1)Answer
20
The array starts at index 0, so index 1 holds the second value, 20.
-
What does
(//)do?Answer
Returns a new array with the listed positions replaced
The update is functional: a new array is returned and the old one is untouched.
-
What does this program print?
module Main (main) where import Data.Array (listArray, bounds) main :: IO () main = print (bounds (listArray (2, 5) [1, 2, 3, 4 :: Int]))Answer
(2,5)
The bounds are the pair given to listArray, whatever the elements are.
-
What does
accumArray (+) 0 (1, 3) [(1, 2), (1, 5)]give at index 1?Answer
7
The two values for index 1 are combined with + on top of the starting 0.
-
Why is an array lookup constant time?
Answer
The elements are contiguous and the index arithmetic is direct
An array is a block of memory and the index gives the offset in one step.
-
Which type is the immutable array of
Data.Array?Answer
Array i eArray is the pure one; IOArray and STArray are the mutable ones for loops.
-
What must the index type of an array be?
Answer
An instance of
IxIx gives the range as a list of indices, which is what bounds and indices need.
The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev