Image Rotation: Mutable Arrays in Haskell

Written By James Bowen

In last week’s article, we took our first step into working with multi-dimensional arrays. Today, we’ll be working with another Matrix problem that involves in-place mutation. The Haskell solution uses the MArray interface, which takes us out of our usual

The MArray interface is a little tricky to work with. If you want a full overview of the API, you should sign up for our Solve.hs course, where we cover mutable arrays in module 2!

The Problem

Today’s problem is Rotate Image. We’re going to take a 2D Matrix of integer values as our input and rotate the matrix 90 degrees clockwise. We must accomplish this in place, modifying the input value without allocating a new Matrix. The input matrix is always “square” (n x n).

Here are a few examples to illustrate the idea. We can start with a 2x2 matrix:

1  2   |   3  1
3  4   |   4  2

The 4x4 rotation makes it more clear that we’re not just moving numbers one space over. Each corner element will go to a new corner. You can also see how the inside of the matrix is also rotating:

1  2  3  4    |  13  9  5  1
5  6  7  8    |  14 10  6  2
9  10 11 12   |  15 11  7  3
13 14 15 16   |  16 12  8  4

The 3x3 version shows how with an odd number of rows and columns, the inner most number will stand still.

1  2  3   |   7  4  1
4  5  6   |   8  5  2
7  8  9   |   9  6  3

The Algorithm

While this problem might be a little intimidating at first, we just have to break it into sufficiently small and repeatable pieces. The core step is that we swap four numbers into each other’s positions. It’s easy to see, for example, that the four corners always trade places with one another (1, 4, 13, 16 in the 4x4 example).

What’s important is seeing the other sets of 4. We move clockwise to get the next 4 values:

  1. The value to the right of the top left corner
  2. The value below the top right corner
  3. The value to the left of the bottom right corner
  4. The value above the bottom left corner.

So in the 4x4 example, these would be 2, 8, 15, 9. Then another group is 3, 12, 14, 15.

Those 3 groups are all the rotations we need for the “outer layer”. Then we move to the next layer, where we have a single group of 4: 6, 7, 10, 11.

This should tell us that we have a 3-step process:

  1. Loop through each layer of the matrix
  2. Identify all groups of 4 in this layer
  3. Rotate each group of 4

It helps to put a count on the size of each of these loops. For an n x n matrix, the number of layers to rotate is n / 2, rounded down, because the inner-most layer needs no rotation in an odd-sized matrix.

Then for a layer spanning from column c1 to c2, the number of groups in that layer is just c2 - c1. So for the first layer in a 4x4, we span columns 0 to 3, and there are 3 groups of 4. In the inner layer, we span columns 1 to 2, so there is only 1 group of 4.

Rust Solution

As is typical, we’ll see more of a loop structure in our Rust code, and a recursive version of this solution in Haskell. We’ll also start by defining various terms we’ll use. There are multiple ways to approach the details of this problem, but we’ll take an approach that maximizes the clarity of our inner loops.

We’ll define each “layer” using the four corner coordinates of that layer. So for an n x n matrix, these are (0,0), (0, n - 1), (n - 1, n - 1), (n - 1, 0). After we finish looping through a layer, we can simply increment/decrement each of these values as appropriate to get the corner coordinates of the next layer ((1,1), (1, n - 2), etc.).

So let’s start our solution by defining the 8 mutable values for these 4 corners. Each corner (top/left/bottom/right) has a row R and column C value.

pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
    let n = matrix.len();
    let numLayers = n / 2;
    let mut topLeftR = 0;
    let mut topLeftC = 0;
    let mut topRightR = 0;
    let mut topRightC = n - 1;
    let mut bottomRightR = n - 1;
    let mut bottomRightC = n - 1;
    let mut bottomLeftR = n - 1;
    let mut bottomLeftC = 0;
    ...
}

It would be possible to solve the problem without these values, determining coordinates using the layer number. But I’ve found this to be somewhat more error prone, since we’re constantly adding and subtracting from different coordinates in different combinations. We get the number of layers from n / 2.

Now let’s frame the outer loop. We conclude the loop by modifying each coordinate point. Then at the beginning of the loop, we can determine the number of “groups” for the layer by taking the difference between the left and right column coordinates.

pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
    ...
    for i in 0..numLayers {
        let numGroups = topRightC - topLeftC;

        for j in 0..numGroups {
            ...
        }

        topLeftR += 1;
        topLeftC += 1;
        topRightR += 1;
        topRightC -= 1;
        bottomRightR -= 1;
        bottomRightC -= 1;
        bottomLeftR -= 1;
        bottomLeftC += 1;
    }
}

Now we just need the logic for rotating a single group of 4 points. This is a 5-step process:

  1. Save top left value as temp
  2. Move bottom left to top left
  3. Move bottom right to bottom left
  4. Move top right to bottom right
  5. Move temp (original top left) to top right

Unlike the layer number, we’ll use the group variable j for arithmetic here. When you’re writing this yourself, it’s important to go slowly to make sure you’re using the right corner values and adding/subtracting j from the correct dimension.

pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
    ...
    for i in 0..numLayers {
        let numGroups = topRightC - topLeftC;

        for j in 0..numGroups {
            let temp = matrix[topLeftR][topLeftC + j];
            matrix[topLeftR][topLeftC + j] = matrix[bottomLeftR - j][bottomLeftC];
            matrix[bottomLeftR - j][bottomLeftC] = matrix[bottomRightR][bottomRightC - j];
            matrix[bottomRightR][bottomRightC - j] = matrix[topRightR + j][topRightC];
            matrix[topRightR + j][topRightC] = temp;
        }

        ... // (update corners)
    }
}

And then we’re done! We don’t actually need to return a value since we’re just modifying the input in place. Here’s the full solution:

pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
    let n = matrix.len();
    let numLayers = n / 2;
    let mut topLeftR = 0;
    let mut topLeftC = 0;
    let mut topRightR = 0;
    let mut topRightC = n - 1;
    let mut bottomRightR = n - 1;
    let mut bottomRightC = n - 1;
    let mut bottomLeftR = n - 1;
    let mut bottomLeftC = 0;
    for i in 0..numLayers {
        let numGroups = topRightC - topLeftC;

        for j in 0..numGroups {
            let temp = matrix[topLeftR][topLeftC + j];
            matrix[topLeftR][topLeftC + j] = matrix[bottomLeftR - j][bottomLeftC];
            matrix[bottomLeftR - j][bottomLeftC] = matrix[bottomRightR][bottomRightC - j];
            matrix[bottomRightR][bottomRightC - j] = matrix[topRightR + j][topRightC];
            matrix[topRightR + j][topRightC] = temp;
        }

        topLeftR += 1;
        topLeftC += 1;
        topRightR += 1;
        topRightC -= 1;
        bottomRightR -= 1;
        bottomRightC -= 1;
        bottomLeftR -= 1;
        bottomLeftC += 1;
    }
}

Haskell Solution

This is an interesting problem to solve in Haskell because Haskell is a generally immutable language. Unlike Rust, we can’t make values mutable just by putting the keyword mut in front of them.

With arrays, we can modify them in place though using the MArray monad class. We won’t go through all the details of the interface in this article (you can learn about all that in Solve.hs Module 2). But we’ll start with the type signature:

rotateImage :: (MArray array Int m) => array (Int, Int) Int -> m ()

This tells us we are taking a mutable array, where the array type is polymorphic but tied to the monad m. For example, IOArray would work with the IO monad. We don’t return anything, because we’re modifying our input.

We still begin our function by defining terms, but now we need to use monadic actions to retrieve even the bounds our our array.

rotateImage :: (MArray array Int m) => array (Int, Int) Int -> m ()
rotateImage arr = do
  ((minR, minC), (maxR, maxC)) <- getBounds arr
  let n = maxR - minR + 1
  let numLayers = n `quot` 2
  ...

Our algorithm has two loop levels. The outer loop goes through the different layers of the matrix. The inner layer goes through each group of 4 within the layer. In Haskell, both of these loops are recursive, monadic functions. Our Rust loops treat the four corner points of the layer as stateful values, so these need to be inputs to our recursive functions. In addition, each function will take the layer/group number as an input.

rotateImage :: (MArray array Int m) => array (Int, Int) Int -> m ()
rotateImage arr = do
  ((minR, minC), (maxR, maxC)) <- getBounds arr
  let n = maxR - minR + 1
  let numLayers = n `quot` 2
  ...
  where
    rotateLayer tl@(tlR, tlC) tr@(trR, trC) br@(brR, brC) bl@(blR, blC) n = ...
    
    rotateGroup (tlR, tlC) (trR, trC) (brR, brC) (blR, blC) j = ...

Now we just have to fill in these functions. For rotateLayer, we use the “layer number” parameter as a countdown. Once it reaches 0, we’ll be done. We just need to determine the number of groups in this layer using the column difference of left and right. Then we’ll call rotateGroup for each group.

We make the first call to rotateLayer with numLayers and the original corners, coming from our dimensions. When we recurse, we add/subtract 1 from the corner dimensions, and subtract 1 from the layer number.

rotateImage :: (MArray array Int m) => array (Int, Int) Int -> m ()
rotateImage arr = do
  ((minR, minC), (maxR, maxC)) <- getBounds arr
  let n = maxR - minR + 1
  let numLayers = n `quot` 2
  rotateLayer (minR, minC) (minR, maxC) (maxR, maxC) (maxR, minC) numLayers
  where
    rotateLayer _ _ _ _ 0 = return ()
    rotateLayer tl@(tlR, tlC) tr@(trR, trC) br@(brR, brC) bl@(blR, blC) n = do
      let numGroups = ([0..(trC - tlC - 1)] :: [Int])
      forM_ numGroups (rotateGroup tl tr br bl)
      rotateLayer (tlR + 1, tlC + 1) (trR + 1, trC - 1) (brR - 1, brC - 1) (blR - 1, blC + 1) (n - 1)
    
    rotateGroup (tlR, tlC) (trR, trC) (brR, brC) (blR, blC) j = ...

And how do we rotate a group? We use the same five steps we took in Rust. We save the top left as temp and then move the values around. We use the monadic functions readArray and writeArray to perform these actions in place on our Matrix.

rotateImage :: (MArray array Int m) => array (Int, Int) Int -> m ()
rotateImage arr = do
  ...
  where
    ...
    
    rotateGroup (tlR, tlC) (trR, trC) (brR, brC) (blR, blC) j = do
      temp <- readArray arr (tlR, tlC + j)
      readArray arr (blR - j, blC) >>= writeArray arr (tlR, tlC + j)
      readArray arr (brR, brC - j) >>= writeArray arr (blR - j, blC)
      readArray arr (trR + j, trC) >>= writeArray arr (brR, brC - j)
      writeArray arr (trR + j, trC) temp

Here’s the full implementation:

rotateImage :: (MArray array Int m) => array (Int, Int) Int -> m ()
rotateImage arr = do
  ((minR, minC), (maxR, maxC)) <- getBounds arr
  let n = maxR - minR + 1
  let numLayers = n `quot` 2
  rotateLayer (minR, minC) (minR, maxC) (maxR, maxC) (maxR, minC) numLayers
  where
    rotateLayer _ _ _ _ 0 = return ()
    rotateLayer tl@(tlR, tlC) tr@(trR, trC) br@(brR, brC) bl@(blR, blC) n = do
      let numGroups = ([0..(trC - tlC - 1)] :: [Int])
      forM_ numGroups (rotateGroup tl tr br bl)
      rotateLayer (tlR + 1, tlC + 1) (trR + 1, trC - 1) (brR - 1, brC - 1) (blR - 1, blC + 1) (n - 1)
    
    rotateGroup (tlR, tlC) (trR, trC) (brR, brC) (blR, blC) j = do
      temp <- readArray arr (tlR, tlC + j)
      readArray arr (blR - j, blC) >>= writeArray arr (tlR, tlC + j)
      readArray arr (brR, brC - j) >>= writeArray arr (blR - j, blC)
      readArray arr (trR + j, trC) >>= writeArray arr (brR, brC - j)
      writeArray arr (trR + j, trC) temp

Conclusion

We’ve got one more Matrix problem to solve next time, and then we’ll move on to some other data structures. To learn more about using Data Structures and Algorithms in Haskell, you take our Solve.hs course. You’ll get the chance to write a number of data structures from scratch, and you’ll get plenty of practice working with them and using them in algorithms!

James Bowen
Next

Binary Search in a 2D Matrix