**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

The signature for List.fold_left is (‘b -> ‘a -> ‘b) -> ‘a list -> ‘bf(..f(f((f s i0 ) i1)i2)..) in

(‘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:

Behind the scenes, List.fold_left is implemented as:[<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)

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.let rec fold_left f s l = match l with ¦ [] -> s ¦ (h::t) -> fold_left f (f s h) t

**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.

The signature for the function is (‘a -> ‘a -> ‘a) -> ‘a list -> ‘af(..f(f((f i0 i1) i2)i3)..) in

Here’s an example:(‘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

Total = 362880 You can also do a short hand operator with fold1_left, like so:let list = [1 .. 9] let total = List.fold1_left (fun x y -> x * y) list

let total = List.fold1_left (+) listTotal = 45 List.fold1_left behind the scenes is implemented like so:

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).let fold1_left f l = match l with ¦ [] -> invalid_arg "List.fold1_left" ¦ (h::t) -> fold_left f h 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 jnThe 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.Here’s an example:‘c – The seed value ‘a list – The first List ‘b list – The second list ‘c – The return value

Answer = 65 Here is how is this function implemented.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

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.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"

## 1 comment:

Hey, Fantastic post. I also started F# recently and been going through project euler. Found this a great resource for understanding the functionality provided for Lists.

Great Job. I will be following your blog closely.

Post a Comment