19 Fold

List.fold_right folds in values of the list from the right to the left. You can think of this as "accumulating an answer"

• Repeatedly applies f to an element of a list and the "answer so far"
• Folds in elements from the right

Let's implement it ourselves:

let rec fold_right f lst acc = 
	match lst with
	| [] -> acc
	| h :: t -> f h (fold_right f t acc);;

val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>

List.fold_left does the opposite, it folds from the left. Let's implement it!

let rec fold_left f acc lst =
	match lst with
	| [] -> acc
	| h :: t -> fold_left f (f acc h) t

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

Mnemonic: The accumulator goes on the side of the list that the function is named.

Why do we bother having both a fold_left and a fold_right. Let's try addition:

• left to right: $((0+1)+2)+3 = 6$
• right to left: $1+(2+(3+0)) = 6$.

They're both the same! But what about subtraction?

• left to right $((0-1)-2)-3) = -6$
• right to left $1-(2-(3-0))=2$

In general, if the answer isn't associative and commutative, fold left and fold right do different things.

In addition, fold_left is tail recursive; however, fold_right isn't. There's work to be done after the recursive call in fold_right.

If you want a tail recursive from the right, you can reverse the list, then fold_right. This requires traversing the list an extra time, but doesn't increase asymptotic complexity.