Mutable Arrays

In the next three subsections, we will discuss three examples of how immutable arrays combined with laziness allow us to implement interesting algorithms that seemingly require efficient element-by-element array updates. This works for many problems but certainly not for all. There are algorithms where we simply do need arrays that we update one element at a time. These algorithms cannot be implemented efficiently using immutable arrays.

To implement such algorithms in Haskell, we have two options. The first one is to use binary search trees instead of arrays as our underlying data structure. Note that an array simply associates values with array indices. We can clearly represent this association using a binary search tree. The advantage of binary search trees is that they do support efficient element-by-element updates, at a cost of \(O(\lg n)\) time per update. Thus, we obtain reasonably efficient implementations of algorithms that require such fine-grained array updates, but not quite as efficient as if we had used a mutable array in an imperative language. We pay a logarithmic overhead for binary search tree operations that would have been implemented using constant-time array accesses in an imperative program.

If this logarithmic slow-down is unacceptable, Haskell does offer us mutable arrays, arrays that can be updated in place, at constant cost per update. But there's a price to pay. Such destructive array updates are side effects, which are not supported in purely functional code. Haskell uses monads to provide a way to look at side effects through a functional lens and thus support side effects in Haskell code. Most monads are simply convenience wrappers that make the purely functional implementation of, for example, computations with state more elegant to work with. The only monads that support true side effects are the IO monad and the ST monad. Correspondingly, we have IOArrays and STArrays that support in-place constant-time updates using code implemented in one of these monads. Since we have not discussed monads at all yet, I will not discuss the details of working with mutable arrays here. Nor will I do this when we talk about monads. It's really a topic for you to explore on your own once you are sufficiently proficient in Haskell programming. Indeed, it is a good exercise to program purely functionally and avoid using the escape hatch of the ST monad until you know you really, really need it. Apart from efficiency, you should never have a reason to use it. The IO monad is another story, as we need it every time we want to perform any kind of I/O such as printing results of a computation on screen or reading and writing a file.