Bulk Updates
I pointed out before that array updates are inefficient, because every time we
"update" an array, we need to make a copy of the whole array, with the updated
array slots storing new values. accumArray was one function that allowed us to
sidestep this issue. In an imperative language, our implementation of
countOccurrences would have started by initializing a count array with all
entries set to 0. Then we would iterate over the characters in the input string
and increase the count of each character by 1. accumArray does the exact same
thing, but it does this as a single operation, requiring all the "updates" to be
given as one list. From the outside, accumArray is simply a function that
builds an array from a list, so no copying of the array is required.
Instead of building an array from a list, we can also take an existing array and construct a new array from it whose entries have been updated. Since updating individual array cells is inefficient, we are encouraged to perform bulk updates, given an entire list of updates to be performed in a single update operation. These updates come in two flavours.
(//)
First, we have
(//) :: Ix i => Array i e -> [(i, e)] -> Array i e
Given an array arr and a list of updates upds, arr // upds constructs a
new array where each index-value pair in upds overwrites the entry at the
given index in arr with the associated value. For example,
>>> arr = array (1,3) [(3,'x'),(1,'a'),(2,'d')]
>>> arr' = arr // [(3,'t'),(2,'e')]
>>> arr'!1
'a'
>>> arr'!2
'e'
>>> arr'!3
't'
The entries in the first slots of arr and arr' are the same, because the
update list [(3,'t'),(2,'e')] does not contain an entry with index 1. The
entry in position 2 is overwritten with 'e'. The entry in position 3 is
overwritten with 't'.
(//) treats multiple entries with the same index in the same way that array
does: the last entry with the given index determines the value stored in the
final array, that is, the last entry overwrites all entries that came before it.
Formally, we have
array rng xs = listArray rng (repeat undefined) // xs
and
arr // upds = array (bounds arr) (assocs arr ++ upds)
So array behaves as if we initialized all array entries to undefined and
then we updated the array entries using the updates given in xs. Conversely,
arr // upds does the same as building a new array with the same bounds as
arr. The values in this new array are the same as in arr, extracted using
assocs arr, except that the updates in upds overwrite some of these values
because we put the updates in upds after the elements in assocs arr in the
list of index-value pairs used to populate the new array.
accum
The other update operation we have is accum. Just as (//) is the sibling of
array, accum is the sibling of accumArray. Its type is
accum :: Ix i => (e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
Instead of building an array from scratch where every array entry has been
initialized to the same value, accum takes an existing array and a list of
updates. It then uses the accumulator function given as the first argument to
combine the existing array entries with the values given in the list of updates.
Again, we can simulate accumArray in terms of accum:
accumArray f init rng xs = accum f (listArray rng (repeat init)) xs