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
    xs.Head.ToString()
  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:

• Array.fold
• List.fold
• Seq.fold
• Set.fold
• Map.fold

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