This article will go over many of the techniques I use for these purposes.
Suppose you want to print an identity matrix:
In an imperative language like Perl, you’ll likely split this into 4 steps:
In Haskell, we run into trouble when we realize there’s no built-in mutating assignment operation:
writeArray array i j k is supposed to be equivalent to Perl’s
Each call to
sequence_ executes a list of actions. The
do notation in List context is a way of stretching the list generator notation out to multiple lines: Step 2 above is equivalent to
Notice that the indices are one-based(
[1..10]) and not zero-based(
[0..9]), because I declared the boundaries of the array to be
The code above compiles but fails to run because
writeArray is not defined. There’s no way to define
writeArray, because values are immutable in Haskell. We use
writeArray in 2 places: When we initialize the array, and when we modify the diagonal. We can initialize the array when we declare it, so that removes the first issue:
do is in List context because
array expect a List. In
do is in IO context, which allows us to define an action that chains together multiple dependent actions.
If you run this sample, you should see a 10x10 matrix with all zeroes:
Steps 1,2, and 4 are easy. Our problem is Step 3: We have no way to define
writeArray, since the array is immutable.
If arrays are immutable, could we somehow make it mutable?
For arrays specifically, there is a mutable variant
IOArray that lets you allocate, read, and write mutable arrays in
IO context. It even has a
writeArray function that is very similar to the one we need. Here’s how you would use it:
let _ = arr :: IOArray (Int,Int) Integer is a way of giving a type signature to
People have written immutable, mutable, contiguous, automatically-parallelized, GPU-accelerated, and other types of arrays. It’s always a good idea to choose the right data structure when writing a program in any language.
In general, not every useful data structure automatically comes with a mutable variant. You can always write one yourself, but for the rest of this article we’ll assume the array is immutable so that you can use the techniques here more generally.
References are normally transparent in imperative languages: C++ has the concept of an lvalue and rvalue because reads and writes are not explicitly written out. Also, stack-allocated declarations look similar to assignments, so it’s not clear that allocation is happening:
Pointers make the allocation and indirect access a little more explicit. However,
*x can involve either a read or write depending on the context:
IORef, that is equivalent to:
Like pointers, a reference to an integer is different from an integer. I’ve left commented-out type signatures above to show this.
newIORefcreates a mutable reference.
readIORefreads the reference
writeIORefchanges it to point to a new value. (Old values are automatically garbage-collected.)
All of these need to be in IO context, because reads and writes can’t be reordered.
modifyIORef' will read the value using a reference, apply a function to it, and write the value back. You almost always want to use the strict version
modifyIORef' rather than the lazy version
modifyIORef, because it has more predictable performance.
arr // [(index, value)] is a new array with an updated value at index. It does not read or write to memory -
modifyIORef will do the reading and writing - it simply is the new array.
[(index, value)] is a list because
(//) allows us to update multiple values at once, though I only update a single value each time here.
One shortcoming of this technique is that it requires your code to be in
writeArray all use
IO. If you want to add mutable references throughout your code, you’ll have to change everything to be in IO context. If you want to actually mutate global variables, this is necessary; but see the
ST monad below to avoid this if you only need mutation within a single function.
While this is the most direct way to do what we want, Haskellers usually get by without any mutation. How would that work?
The Haskell Way
We know how to create new arrays, but updating them is tricky. So one way around this is to create a new array, and have later code use it. This is what I would likely write in real code:
(//) takes a list of updates, so we can calculate all the places that we need to update and pass them in all at once.
arr is the original zero matrix, while
arr2 is the updated identity matrix. We make sure that
printElement takes the array as a parameter, and call it with
In subsequent sections, we’ll mostly show various ways to implement
updateArray using mutation-like constructs. You can assume the rest of the code remains the same.
In Haskell, later variables with the same name “shadow” earlier variables, so we can pretend that we’ve updated the array in-place by giving the new array the same name:
updateArray in the above code is supposed to be similar to this Perl:
Another way of writing it in Haskell that avoids the deep nesting is:
do notation above is in
Identity context, which is a way of chaining together ordinary Haskell values and functions using the
do syntax. The compiler should convert it to deeply-nested case statements, or something equivalent.
I needed to use
do notation or
case because pattern matches are non-recursive. This will produce an infinite loop, because
let bindings are recursive by default; so
arr will be defined in terms of itself, not the previous array.
There are two shortcomings with using shadowing as a replacement for mutation:
- It’s a little verbose to repeat the variable name twice when “reading” and “writing”.
- It works when there are a fixed number of updates(
10), but not in e.g. a while loop that repeatedly updates a variable.
Look back at this example from Shadowing:
Since we don’t really do anything with the variable other than feed it into the next binding, some Haskellers would remove the variables and compose the functions together:
This works okay when we have a chain updating 1 variable. You can extend it to more by using a tuple:
Here, we make the indices
j part of the state, and increment them after each application of
updateNext. At the end, we would get the new array,
j; but we only care about the array, so
One shortcoming of this technique is that you have to ensure that the state parameter is always last, to compose the functions. See the
State monad for a way of hiding the state paremeter.
The most powerful way to write high-performance Haskell is to make your state explicit, and call an inner function written in tail-recursive style. I’ll add the variables to the previous example:
One problem with this is that we’re duplicating the same statement 10 times. It’s a little silly to have 18 lines when the Perl is only 3:
for loop consists of 4 components:
- An initial state:
my $idx = 0, and
- A condition that reads the state:
$idx < $size
- Statements advancing the state:
$array->[$idx]->[$idx] = 1;
- (Optional) A way to convert the state into a return value:
$arrayafter the loop.
Here is the most general way to convert a loop into a tail-recursive
With this, it’s mechanical to replace any simple for loops with a tail-recursive function. The only loops that can’t be converted are those that do something other than pure computation, such as write to a logfile or connect to a database. For those, see Recursive IO below.
Here’s a shorter function that I would be more likely to use in real code:
In the Function Composition section, we saw that we can emulate mutable variables by making the state the last parameter in a sequence of functions and composing them.
State monad is a way of automatically threading this state parameter to all code that uses it. I’ll add the variables back to the previous example:
A value of type
State s a is a value of type
a that implicitly reads and writes a state parameter of type
s. You almost always want the strict version. Here is the above code written to use
The pattern match
(i, arr) <- get pattern matches the state that is implicitly being passed around.
put (i+1, arr') passes a new state to the next statement.
Take a moment to see how the tuple is being passed along. It’s entirely equivalent to the
let binding example.
This can also be written much shorter:
You can also mix tail recursive style to emulate loops that change mutable variables:
IORef example had the disadvantage that it required code to be in
IO context to read or write references. Code in
ST context also allows mutable variables, and can be embedded anywhere. Instead of an
IORef, you’ll want an
The difference between
IO is that
ST only allows references to be local to the
runST call. Mutable local variables have no external side effects. They are completely safe to use, which is why we can embed them anywhere. The compiler ensures that the references never escape.
IO lets you use global variables, write files, connect to databases, and all sorts of other things.
In Shadowing, we learned that you can sometimes simulate mutation by creating a new value with the same name, rather than updating the existing value. In State Monad, we learned that you can make this more composable by hiding the parameters and implicitly threading them along.
ImplicitParams is a language extension that allows you to thread hidden parameters anywhere in your code.
Their chief advantage is that you can add them to any existing implementation code and it will still compile. You may need to update type signatures, but in well-structured code you’ll often only have a single program-specific type alias to change.
I’ve used them for global configuration before: Imagine connecting to a database on program startup to retrieve configuration information, which is accessible throughout most of the program. You usually wouldn’t use them for inner loops or computation, so I’ve changed the example for this section.
Suppose we’ve unwisely chosen a
List as the data structure for our program, and it uses too many
List-specific utility functions to easily change to a different data type. Eventually, we plan to switch to an array or
Data.Vector, but in the meantime there are performance issues because we use
length everywhere(which is for linked lists). You can use Implicit Parameters to calculate the length of a list once, and pass it around.
Here’s the current code:
length arr > 10 is slowing down the calculation. Add the implicit parameter:
The important thing above is that we added the implicit parameter without needing to change any of the code in the calculation: We only changed the type signature, and set
?length once near the beginning of our program. Of course, now that it’s available, we can temporarily fix the performance problem by using it:
You can mix recursive style with
IORef to write code that feels like C in Haskell. Here’s the plain version:
And here’s a few variations with some helper functions:
when instead of having an empty
replicateM_ to repeat the action rather than hand-coding a recursive loop:
modifyIORef' rather than reading and writing:
All-in-all, it’s not the most elegant, but it gets the job done.
You’ve seen a lot of different ways to do the same thing. Hopefully some of them are new, and help you port your own imperative thinking and code over to Haskell. Send me a message on Twitter if this helped at all.
The best one-liner to create the array is probably this:
- Thanks to Tome Jaguar for the concept and code used in the Mutable Arrays section!
About the Author
Michael Burge helps companies efficiently process their large datasets. This includes everything from database and schema design for new projects, problem diagnosis and repair for existing projects hitting scaling limits, and even bespoke SQL compilers and databases for exceptionally difficult cases. Hire Michael to benefit from his extensive knowledge and experience.