# Mark Needham

Thoughts on Software Development

## Algorithms: Flood Fill in Haskell – Abstracting the common

with one comment

In the comments of my blog post describing the flood fill algorithm in Haskell David Turner pointed out that the way I was passing the grid around was quite error prone.

```floodFill :: Array (Int, Int) Colour -> (Int, Int) -> Colour -> Colour -> Array (Int, Int) Colour floodFill grid point@(x, y) target replacement = if((not \$ inBounds grid point) || grid ! (x,y) /= target) then grid else gridNorth where grid' = replace grid point replacement gridEast = floodFill grid' (x+1, y) target replacement gridWest = floodFill gridEast (x-1, y) target replacement gridSouth = floodFill gridWest (x, y+1) target replacement gridNorth = floodFill gridSouth (x, y-1) target replacement```

I actually did pass the wrong grid variable around while I was writing it and ended up quite confused as to why it wasn’t working as I expected.

David’s suggestion based on the above version of the algorithm was that I might want to use the state monad to thread state rather than explicitly passing it around like I am here.

I had a go at writing the function using the state monad but realised while doing so that rather than doing that I could fold over a cells neighbours rather than using the state monad to thread state.

I didn’t see the ‘neighbours’ concept the first time I wrote it but David wrote a version of the algorithm in which he introduced that.

This is the resulting function:

```floodFill :: Array (Int, Int) Colour -> (Int, Int) -> Colour -> Colour -> Array (Int, Int) Colour floodFill grid point target replacement = if(target == replacement) then grid else let gridWithSquareReplaced = if onGrid point then grid // [(point, replacement)] else grid validNeighbours = filter (onGrid `and` sameAsTarget) neighbours in   foldl (\grid point -> floodFill grid point target replacement) gridWithSquareReplaced validNeighbours   where neighbours = let (x,y) = point in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)] sameAsTarget point = grid ! point == target onGrid = inRange \$ bounds grid   and :: (a -> Bool) -> (a -> Bool) -> a -> Bool and f g x = f x && g x```

I initially get all of the neighbouring squares but then filter those out if they don’t fit on the grid or aren’t of the required colour. We can then use ‘foldl’ to iterate over each neighbour passing the grid along as the accumulator.

David also wrote a more succinct function to work out whether or not a value fits on the grid so I’ve stolen that as well!

I’m still not sure I totally understand when I should be using ‘let’ and ‘where’ but in this example the functions I’ve put in the ‘where’ section are helper functions whereas the values I defined in the ‘let’ section are domain concepts.

Whether that’s the correct way to think of the two I’m not sure!

Written by Mark Needham

April 17th, 2012 at 7:22 am

Tagged with ,

## Algorithms: Flood Fill in Haskell

Flood fill is an algorithm used to work out which nodes are connected to a certain node in a multi dimensional array. In this case we’ll use a two dimensional array.

The idea is that we decide that we want to change the colour of one of the cells in the array and have its immediate neighbours who share its initial colour have their colour changed too i.e. the colour floods its way through the grid.

The algorithm is described on Wikipedia like so:

Flood-fill (node, target-color, replacement-color):

1. If the color of node is not equal to target-color, return.
2. Set the color of node to replacement-color.
• Perform Flood-fill (one step to the west of node, target-color, replacement-color).
• Perform Flood-fill (one step to the east of node, target-color, replacement-color).
• Perform Flood-fill (one step to the north of node, target-color, replacement-color).
• Perform Flood-fill (one step to the south of node, target-color, replacement-color).
3. Return.

I decided to have a go at implementing it in Haskell and ended up with the following code:

```import Data.Array data Colour = White | Black | Blue | Green | Red deriving (Show, Eq)```
```inBounds :: Array (Int, Int) Colour -> (Int, Int) -> Bool inBounds grid (x, y) = x >= lowx && x <= highx && y >= lowy && y <= highy where ((lowx, lowy), (highx, highy)) = bounds grid   replace :: Array (Int, Int) Colour -> (Int, Int) -> Colour -> Array (Int, Int) Colour replace grid point replacement = if inBounds grid point then grid // [(point, replacement)] else grid```
```floodFill :: Array (Int, Int) Colour -> (Int, Int) -> Colour -> Colour -> Array (Int, Int) Colour floodFill grid point@(x, y) target replacement = if((not \$ inBounds grid point) || grid ! (x,y) /= target) then grid else gridNorth where grid' = replace grid point replacement gridEast = floodFill grid' (x+1, y) target replacement gridWest = floodFill gridEast (x-1, y) target replacement gridSouth = floodFill gridWest (x, y+1) target replacement gridNorth = floodFill gridSouth (x, y-1) target replacement```

Since we can’t mutate the array, but only create new instances of it, we have to pass it onto the next recursive call such that the recursive call to the ‘East’ passes its result to the one recursing to the ‘West’ and so on.

It seemed to be easier to check that the square we wanted to change was actually in the grid in the replace function rather than before calling it so I pushed the logic into there. The bounds function was useful for allowing me to work out if we were still on the grid.

```> printGrid \$ (toComplexArray [[White, White, White, Blue, Blue], [Blue, White, Blue, Blue, Blue], [Blue, Blue, Blue, Green, Green], [Green, Red, Blue, Black, Black], [Blue, Blue, Blue, Green, Blue]])   White White White Blue Blue Blue White Blue Blue Blue Blue Blue Blue Green Green Green Red Blue Black Black Blue Blue Blue Green Blue```

Let’s say we want to change the ‘Blue’ value on the second line down, third row across (position 1,2) in the array to be ‘Red’:

```> printGrid \$ floodFill (toComplexArray [[White, White, White, Blue, Blue], [Blue, White, Blue, Blue, Blue], [Blue, Blue, Blue, Green, Green], [Green, Red, Blue, Black, Black], [Blue, Blue, Blue, Green, Blue]]) (1,2) Blue Red   White White White Red Red Red White Red Red Red Red Red Red Green Green Green Red Red Black Black Red Red Red Green Blue```

The toComplexArray function is used to convert a list into an ‘Array’ because it’s much easier to create a list for testing purposes. The code for that is on github if you’re interested.

I described the printGrid function in my last post and the rest of the code is on my github haskell repository.

Written by Mark Needham

April 7th, 2012 at 12:25 am