Arrays and Array Functions

As discussed earlier, arrays are used much less often in Haskell than lists, because large chunks of memory treated as immutable entities are usually inefficient to manipulate. The recursive definition of lists, and their ability to share nodes, allows for much more fine-grained elementwise manipulations of lists.

Nevertheless, arrays have their place in Haskell, because there are some algorithms that require constant-time random access to the elements in a sequence to be implemented efficiently.

Some of these algorithms do indeed require not only constant-time read access to individual array elements but also constant-time write access. Such algorithms cannot be implemented equally efficiently in Haskell unless we are willing to use the escape hatch offered by the ST monad. This is a monad that allows us to program using true side effects, including destructive variable and array updates. It exists exactly because there are some functions that from the outside are perfectly pure—they do nothing but compute their return values from their arguments—but the efficient implementation of these functions requires side effects.

We won't discuss the ST monad or mutable arrays in detail here. Instead, we will look at various functions for immutable arrays. More importantly, we will look at some algorithms that seem to require destructive array updates because they compute each array element from other array elements. As we will see, Haskell's lazy evaluation lets us implement many such algorithms using immutable arrays.