Categories

# F# Friday – The fold Function

Last week we looked at the `reduce` operation, and we observed three properties:

• Using reduce on an empty collection yields an exception.
• You can only reduce a collection to a value of the same type as the elements in the collection.
• The order of the items in the collection (usually) matters.

We also noticed that there are several common operations—sum, product, and string concatenation—that are just special cases of `reduce`.

As it happens, `reduce` is itself a special case of a more fundamental operation: fold. Furthermore, while order still matters, `fold` can

• handle empty collections, and
• reduce a collection of one type to a value of a different type.

Why is that? First, `fold` takes a binary operation just as `reduce` does, but it also takes a starting value in addition to the collection. That is how `fold` can handle empty collections. If the collection is empty, you’re just left with the starting value. Second, because you give `fold` a starting value, that starting value could be of any type; it doesn’t have to match the type of the items in the collection. The reason `reduce` can only reduce a collection to a value of the same type is because the only starting value it has is the first value in the collection.

Let’s put `fold` into action.

### Our Product Line

We implemented a `product` operation last week with `reduce`. Let’s do it this week with `fold`. This figure illustrates what’s going on:

In multiplication, 1 is the identity value. That is, 1 times x is always x. So then, if you want to calculate the product of a list of integers, make your starting value 1. Here is the code:

```let product = [5;3;6] |> List.fold (*) 1
// val product : int = 90
```

Notice, by the way, that we are doing something we did not do last week: Using the multiplication operator as the input function rather than defining a lambda. In other words, it is superfluous to define a lambda `(fun x y -> x * y)` because the multiplication operator `(*)` is already a function that takes two numbers and multiplies them together. Let’s just use it and cut down on some noise!

Now what if the list is empty? We cannot handle an empty list with `reduce`, but what does `fold` do?

```let product = [] |> List.fold (*) 1
// val product : int = 1
```

So then, when `fold` receives an empty collection, it just returns the starting value—in this case, 1.

### Stringing You Along

Last week we also implemented `String.concat` with `reduce`. We can do the same thing with `fold` but there are some gotchas.

Try a straightforward approach:

```let illJoined =
["do";"mi";"sol"]
|> List.fold (fun x y -> x + "-" + y) ""
// val illJoined : string = "-do-mi-sol"
```

Eek! What happened? You don’t want the extra hyphen on the front! You just want hyphens in between the elements!

What if you have a list with just one item?

```let illJoined =
["do"]
|> List.fold (fun x y -> x + "-" + y) ""
// val illJoined : string = "-do"
```

No better. The following figure shows you what has happened:

While `reduce` cannot handle an empty collection, it only starts applying the reduction operation on the first two elements. On the other hand, `fold` applies the binary operation on the starting value and the first item in the list.

To do `String.concat` right with `fold`, you have to account for some special cases:

```let join xs =
if xs |> List.isEmpty then ""
elif xs |> List.length = 1 then
else
xs.Tail
|> List.fold (fun x y -> x + "-" + y) xs.Head
let emptyJoined = join []
// val emptyJoined : string = ""
let singleJoined = join ["do"]
// val singleJoined : string = "do"
let manyJoined = join ["do";"mi";"sol"]
// val manyJoined : string = "do-mi-sol"
```

### From Type to Type

Finally, consider an example of something `fold` can do that `reduce` cannot. If `reduce` receives a list of integers, it can only produce a single integer. If it receives a list of strings, its result is a single string. In contrast, `fold` can take a list of integers and produce a string. Or it could take a list of strings and produce a list of integers.

For instance, you can use `fold` to reverse a list:

```let reversed =
[1..10]
|> List.fold (fun xs x -> x :: xs) []
// val reversed : int list =
//   [10; 9; 8; 7; 6; 5; 4; 3; 2; 1]
```

Notice how the starting value is a list, but the type of the elements in the input list `int`, not `int list`. Because the starting value can be a type that is different from the type of the input list elements, the binary operation can transform the elements in the list to match the type of the starting value. In fact, that is the constraint with `fold`: the type of the result must be type of the starting value. If your starting value is a list, `fold` must return a list. If your starting value is an integer, `fold` must return an integer.

Another example is determining the length of the longest string in a list of strings:

```let longest =
["a";"borborygmus";"sesquipedalian";"small"]
|> List.fold (fun n s -> max n s.Length) 0
// val longest : int = 14
```

Here is the documentation on `fold` in each collection module that defines it:

As an exercise, you could try implementing `map` with `fold`.

## One reply on “F# Friday – The fold Function”

[…] F# Friday â€“ The fold Function –Â Brad Collins […]

This site uses Akismet to reduce spam. Learn how your comment data is processed.