Walking the F# List namespace - Post #2

Continuing on with my walkthrough of the Microsoft.FSharp.Collections.List namespace, I thought I’d give the folding functions a shot. It took me some to time to understand what the functions were accomplishing, but after a few tests, they became clear. List.fold_left: This applies a function to each element in the list and starts an aggregate argument to apply through the rest of the elements. Additionally, the function is given a seed value. The seed value and the first element are passed to the function, the result and the second element are passed to the function, that result and the third element….you get the point. Fold_left can be described as

f(..f(f((f s i0 ) i1)i2)..) in

The signature for List.fold_left is (‘b -> ‘a -> ‘b) -> ‘a list -> ‘b

(‘b -> ‘a -> ‘b) - the function that takes the seed value (‘b) and the
first element (‘a). The function returns ‘b.
‘a list - the source list
‘b - the result

Here’s an example:

[<Test>]
member t.Listfold_left() =
let list = [1 .. 4]
let answer = List.fold_left (fun x y -> x*y) 2 list
Assert.AreEqual(48,answer)

Behind the scenes, List.fold_left is implemented as:

let rec fold_left f s l =
match l with
¦ [] -> s
¦ (h::t) -> fold_left f (f s h) t

Sweet, fold_left is simply a recursive match! The parameters to fold_left are the function (f), the seed (s) and the list (l). If the list is empty, simply return the seed value, because the seed value applied to nothing is the seed value. The (h::t) statement is a thing of beauty, it gets the first element in the list (h) and the rest of the list (t), then calls itself with the function (f), the result of function applied to the seed value and the first element, (f s h) and the tail. List.fold1_left: This applies a function to each element in the list and starts an aggregate argument to apply through the rest of the elements. It takes the first and second elements applies the function, the result and the third function are then given the function, until the end of the list returning the result.

f(..f(f((f i0 i1) i2)i3)..) in 

The signature for the function is (‘a -> ‘a -> ‘a) -> ‘a list -> ‘a

(‘a -> ‘a -> ‘a) - the function to apply the first element to the second
element and return the value
‘a list - the source list
‘a - the return value

Here’s an example:

let list = [1 .. 9]
let total = List.fold1_left (fun x y -> x * y) list

Total = 362880 You can also do a short hand operator with fold1_left, like so:

let total = List.fold1_left (+) list

Total = 45 List.fold1_left behind the scenes is implemented like so:

let fold1_left f l =
match l with
¦ [] -> invalid_arg "List.fold1_left"
¦ (h::t) -> fold_left f h t

Ahhh simplicity! Note the fold1_left function does not have the rec keyword. Given the function (f) and the list (l), the match statement checks for an empty list, if so, throw an invalid argument exception. Next split the list (h::t) and then call fold_left with the function (f), first element (h) and the rest of the list (t).

List.fold_left2: This applies a function to each element in two lists and starts an aggregate calculation based on a seed value and each corresponding list element. Then takes the result and applies it to the second element, and so on. Returning the result. The lists must be the same size. List.fold_left2 can be displayed as

f(..f(f((f s i0 j0 ) i1 j1)i2 j2)..) in jn

The signature for fold_left2 is (‘c -> ‘a -> ‘b –> ‘c) -> ‘c -> ‘a list -> ‘b list -> ‘c

(‘c -> ‘a -> ‘b –> ‘c) - This is a function that takes arguments of ‘c; the seed value, ‘a; an element from list1 and ‘b; an element from list2 and returns ‘c.

‘c – The seed value
‘a list – The first List
‘b list – The second list
‘c – The return value

Here’s an example:

let list1 = [1 .. +2 .. 9]
let list2 = [2 .. + 2 .. 10]
let answer = List.fold_left2 (fun c a b -> c + a + b) 10 list1 list2

Answer = 65 Here is how is this function implemented.

let rec fold_left2 f acc l1 l2 =
     match l1,l2 with
     | [],[] -> acc
     | (h1::t1),(h2::t2) -> fold_left2 f (f acc h1 h2) t1 t2
     | _ -> invalid_arg "List.fold_left2"

This looks very much like the fold_left function above. Fold_left2 takes the parameters of a function (f), the seed value (acc) and two lists (l1) and (l2). The first condition of the match statement checks if both the lists are empty, if so, it returns the seed value (acc). Next it splits the lists by using the (h::t) function and calls itself, by passing the function (f), the result of the function, the seed value and the heads of both lists, (f acc h1 h2) and both list tails.