Understanding the Fold Operation
Tags: functional, fsharp
Published: 2018-12-06 19:34:06

---
title: Understanding the Fold Operation
published: true
description: My simple way to make understandable folds
tags: #fp #fsharp
---

I recently ran across a video by Don Syme called [F# Code I Love](https://www.youtube.com/watch?v=26_W8MmUA60). It details some nice (and naughty 🎄) usage patterns in F#. I was very surprised to see `fold` considered a not-so-nice usage pattern. But I completely understand why.

> 🔎 **What is a fold?**
> Fold is an operation on a collection of data. Lists, sets, hashmaps, etc all are "foldable". Fold takes care of looping through each item in the collection, and lets you define the behavior inside the loop. And in fact, most other collection operations (filter, map, reduce, etc) can be written as fold statements. So fold is a "low-level" way to process items in a list with your own custom behavior. It is for those cases when the built-in collection functions do not have exactly the behavior you need. In Javascript, [`Array.reduce`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce) is the same as fold when called with an initial value. In C#, the LINQ method [`Aggregate`](https://docs.microsoft.com/en-us/dotnet/api/system.linq.enumerable.aggregate?view=netcore-2.2) is the same as fold.

When I first started F#, I found folds hard to understand. So I would typically avoid them and instead write a recursive function to loop through a collection with my custom behavior. (I mean it's pretty bad when recursion is the easy way, right?) But as I refactored the recursive function to isolate the custom behavior from the looping, I noticed that the recursive looping part could be easily replaced with fold.

As time has gone on, I figured out a way to approach folds that makes them easier to start with instead of being a refactored optimization at the end. I will demonstrate with a [coding challenge](https://www.codewars.com/kata/count-of-positives-slash-sum-of-negatives).

> 🏎️ **Challenge**
> Given a list of integers, return the count of positive numbers and the sum of negative numbers.
> When provided the list `[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; -11; -12; -13; -14; -15]`, the solution should return a count of 10 and a sum of -65.


## #1 Define the kind of answer are you expecting with a starting value.

In this case, I want two values as a result.

```fsharp
let (count, sum) = ...
```

Both of them are integers. And for both pieces of the answer, we start with zero and add to it.

```fsharp
let (count, sum) = (0, 0)
```
_If you are unsure what the starting value should be for your particular problem, you can just pick one for now. You can always experiment with it later._

Instead of destructuring the values back into count and sum, I would probably just use a single name for the pair of values.

```fsharp
let initial = (0, 0)
```


## #2 Update the answer based on a single item.

Now that we know what our answer looks like (count and sum), we can define a way to update the answer based on a single input value. I first sketch the `update` function and its arguments.

```fsharp
let update (count, sum) value =
    ...
```

Then I fill in the steps to return the updated count and sum based on the value.

```fsharp
let update (count, sum) value =
    if value > 0 then
        (count + 1, sum)
    elif value = 0 then
        (count, sum)
    else
        (count, sum + value)
```

This reads very well, almost the same as how we explain it to another human. "Update count and sum when given a value. If the value is positive, increase the count but keep the same sum. If the value is zero, keep the same count and sum. Otherwise (value is negative) keep the same count, but add the value to the sum."

_Note: We could save a couple of lines of code by removing the `elif` clause and it would work exactly the same. (Adding zero to the sum is equivalent to returning it as-is.)_


## #3 Now the fold is the easy part.

So the only thing left to do is to process the list itself. And since the input list is provided, we have already defined all the necessary pieces for `fold`. _The fold step always looks similar to this._

```fsharp
let runChallenge inputList =
    inputList |> List.fold update initial
```

Here it is with everything put together.

```fsharp
let initial = (0, 0)

let update (count, sum) value =
    if value > 0 then
        (count + 1, sum)
    elif value = 0 then
        (count, sum)
    else
        (count, sum + value)

let runChallenge inputList =
    inputList |> List.fold update initial
```

And here is how you can run it.

```fsharp
let input = [1;2;3;4;5;6;7;8;9;10;-11;-12;-13;-14;-15]
let (count, sum) = runChallenge input
printfn "Count: %i, Sum: %i" count sum
// Outputs
// Count: 10, Sum: -65
```


## Conclusion

Fold is a really powerful tool to process collections of data. It can allow you to focus on your behavior logic without having to write the looping code. But it can be confusing to use -- you really have to approach it with the right mindset to make the most out of it. The way I have presented here helps me use `fold` in a productive way. Hopefully it will help someone else too.

/∞