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:
The expression 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 (1,1) and (10,10) here:
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:
In arr and main, the do is in List context because sequence_ and array expect a List. In printElement, the 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:
The line let _ = arr :: IOArray (Int,Int) Integer is a way of giving a type signature to arr in do notation.
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:
Using 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.
newIORef creates a mutable reference.
readIORef reads the reference
writeIORef changes 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.
The expression 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 IO context: main, printElement, and 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:
Recall that (//) 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 arr2.
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:
The 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 i and j part of the state, and increment them after each application of updateNext. At the end, we would get the new array, i, and j; but we only care about the array, so getArray discards i and j.
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:
The for loop consists of 4 components:
An initial state: my $idx = 0, and $array
A condition that reads the state: $idx < $size
Statements advancing the state: $idx++, and $array->[$idx]->[$idx] = 1;
(Optional) A way to convert the state into a return value: $array after the loop.
Here is the most general way to convert a loop into a tail-recursive loop function:
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.
The 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 State:
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:
The 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 STRef.
The difference between ST and 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:
The 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:
Use when instead of having an empty else clause:
Use replicateM_ to repeat the action rather than hand-coding a recursive loop:
Use 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!