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

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

  1. Build an array of the squares of 1 to 10 and print the fifth element.
  2. Use accumArray (*) and explain the result for an empty index.
  3. Write a function that returns the element at an index or a default, and compare it with (!).
  4. Compute the sum of an array with elems and with a fold.
  5. Explain why an array index is not checked at compile time and what a safer wrapper would look like.
  6. 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.

  1. 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.

  2. What does table ! 2 do?

    Answer

    Returns the element at index 2

    The (!) operator is the constant-time index lookup.

  3. What happens at table ! 5 when 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

  9. Which type is the immutable array of Data.Array?

    Answer

    Array i e

    Array is the pure one; IOArray and STArray are the mutable ones for loops.

  10. What must the index type of an array be?

    Answer

    An instance of Ix

    Ix 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