Getting Out of the Fold

I did the Advent of Code albeit after the fact. It’s been awhile since I’ve looked at my solutions, I thought it would be good to go back and refactor. This is turning out to be a very good exercise and an indicator of how far I’ve come as a functional programmer.

In my early functional days, learning fold was the pinnacle of accomplishments. Fold can be a difficult function to learn for someone coming from strictly Object Oriented. Fold is a higher order function that takes three parameters. Higher order function is a fancy name for a function that takes another function as a parameter. The three parameters for fold are as follows, a function (known as a folder), an initial state, and a collection of elements. The signature for fold in F# is below, along with a very simple example.

Seq.fold : ('State -> 'T -> 'State) -> 'State -> seq<'T> -> 'State
Seq.fold (fun acc x -> acc + x) 0 [1; 2; 3]

My example? The folder is a function that takes two integers and adds them together. The initial state is zero, and a list that contains the integers 1, 2, and 3. That wasn’t so bad right?

More experienced developers say “That’s not a great example. We already have Seq.sum.” Absolutely, and that’s where I am going. I found I used fold in a lot of cases where there was a much better function.

Spoilers of Advent of Code Day 3

The advent of code day 3 is a perfect example of my use of fold as being a golden hammer. Day 3’s problem is a delivery person is given directions consisting of “<",">“,”v”,”^”. An example of directions could be “^^vv<><>“. That delivery person then delivers packages to the houses at each stop, some houses receive more than one package. What is the number of houses that get packages?

My initial solution using the golden fold.

let move (x,y) = function
    | '^' -> (x, y + 1)
    | 'v' -> (x, y - 1)
    | '<' -> (x - 1, y)
    | '>' -> (x + 1, y)
    | _   -> (x, y)

let countHouses dirs = 
    dirs |> Seq.fold (fun (p,(s : (int * int) Set)) d -> 
            let p' = move p d
            (p', (s.Add p'))) ((0,0), Set.ofList [(0,0)])
    |> fun (_, s) -> s |> Seq.length

The code works, but it’s not all that readable. The state is a tuple containing the current position and a set of houses visited. The folder deconstructs the tuple, moves to the new house, and adds it to the set. The final result of the fold is deconstructed and the set of houses is counted.

Let’s look at how I refactored the solution. This is after some time away from my initial solution.

let countHouses dirs = dirs |> Seq.scan move (0,0) |> Seq.distinct
                       |> Seq.length

Seq.scan is a higher order function that returns a sequence of the intermediate results. It turns out scan is exactly what I needed. You can see scan results in a much nicer solution than fold does.

Fold is a very useful and powerful function, especially when you are getting started. However, it shouldn’t be your go to function for everything. As you gain more experience you learn there are more specific functions that result in code that is a lot easier to reason about. Don’t stop learning when you get into the fold.