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
As it happens,
reduce is itself a special case of a more fundamental operation: fold. Furthermore, while order still matters,
- 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.
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
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
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:
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.
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 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