Folding is typically used to apply a function to a list of data obtaining a single result. Consider the summing up of a list of numbers, the addition routine could be applied using a fold against a list yielding a single number as the result.
Given the image above, we have a list of numbers (9, 4, 2, 4) and a magenta function "Adder" which takes the list of numbers and applies the adder function against them giving us the single output value of 19.
The way in which folding takes place can be thought of as the following.
- Adder 9 4 = 13
- Adder 13 2 = 15
- Adder 15 4 = 19
Or if you dislike that manner of notation.
- 9 + 4 = 13
- 13 + 2 = 15
- 15 + 4 = 19
Typically in functional programming languages there are many different ways to fold a function against a list. In the F# examples which will follow, we'll use fold and reduce, the only difference between the two (at least the only one I know of) is that fold requires an initial value for the function to be applied to, while reduce uses the head of the list as the initial value.
Note that we are using fsi.exe running on Mono.
Given a list of number (x), sum up the values (using 0 as the initial value)
> let x = [4398; 233; 1; 34; 42; 8392; -8];;
val x : int list = [4398; 233; 1; 34; 42; 8392; -8]
> x |> List.fold (+) 0
- ;;
val it : int = 13092
Using reduce gives the same value (and does not require an initial value)
> let x = [4398; 233; 1; 34; 42; 8392; -8];;
val x : int list = [4398; 233; 1; 34; 42; 8392; -8]
> x |> List.fold (+) 0
- ;;
val it : int = 13092
> x |> List.reduce (+)
- ;;
val it : int = 13092
Similarly, we can use folding to find the max and min values (same x as before).
> let x = [4398; 233; 1; 34; 42; 8392; -8];;
val x : int list = [4398; 233; 1; 34; 42; 8392; -8]
> x |> List.reduce (max)
- ;;
val it : int = 8392
> x |> List.reduce (min)
- ;;
val it : int = -8
As you have witness from the code above, folding can be used to apply a function which takes two arguments against a list of values producing one resulting value. Folding is a very useful tool in the functional programming tool belt and is one of the big 3 higher-order functions.
