# List traversal with fold

The first and foremost feature of a functional language is that
variables can't be modified (they are said to be *immutable*). A
direct implication of this is that `for`

and `while`

loops become
useless: since iterations can't modify variables, they are doomed to
reproduce the same calculation each time. In functional programming,
loops are replaced by *recursive functions* to perform iterative
calculations. Let us start with an example.

## Sum of integers

Suppose we'd like to compute the sum of $n$ integers $x_1,\dots,x_n$. A simple recursive formulation for this is to say that we can compute the sum of the first $n-1$ integers and add the last one to the result. In more formal terms:

$$ \begin{aligned} S_n & = & \sum_{i=1}^{n} x_i\\ & = & \sum_{i=1}^{n - 1} x_i + x_n\\ & = & S_{n-1} + x_n \end{aligned} $$

This formulation can be translated *verbatim* in OCaml:

let rec sum xs = match xs with | [] -> 0 | h :: t -> h + sum t ;; val sum : int list -> int = <fun>

If the list is empty, we return the neutral element for the addition
(*i.e.* 0) and if it has at least one element we add it to the sum of
the remaining elements.

## Products of integers

Let's now write a function that computes the *product* of the integers
in a list. We can employ a very similar recursive formulation:

let rec product xs = match xs with | [] -> 1 | h :: t -> h * product t ;; val product : int list -> int = <fun>

Two things have changed:

- the empty list case now returns the neutral element for the
product,
*i.e.*1 - the way the head of the list
`h`

is combined to the result of the recursive call. We now use the product operator`( * )`

.

## Concatenation of strings

Interestingly, the function that concatenates all strings from a list is absolutely similar:

let rec concat xs = match xs with | [] -> "" | h :: t -> h ^ concat t ;; val concat : string list -> string = <fun>

Now the neutral element is an empty string and the head of the list is
combined to the result of the recursive call using the append operator
for strings `( ^ )`

.

## One function to write them all

Since those three functions are so similar, we can in fact see them as
particular instances of a more general function, usually named
`fold`

. We have seen that what differs between two functions is a
binary operation and its associated neutral element. Let's set them as
*parameters*:

let rec fold f e xs = match xs with | [] -> e | h :: t -> f h (fold f e t) ;; val fold : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b = <fun>

The type is now more complex, and displays *type variables*, which
express *typing constraints* between the arguments of `fold`

. Let's
consider them from right to left:

- the third argument is of type
`'a list`

, meaning we're going to process a list of values of type`'a`

(in our case,`'a`

was first`int`

then`string`

). - the second argument is an
*initial value*of type`'b`

(in our case it was successively`0`

,`1`

and`""`

). - the first argument is a function to
*combine*elements of the lists (e.g. integers) with the result we are computing (e.g. sum).

Our three functions can now be rewritten in the following way:

let sum xs = fold ( + ) 0 xs;; val sum : int list -> int = <fun> let prod xs = fold ( * ) 1 xs;; val prod : int list -> int = <fun> let concat xs = fold ( ^ ) "" xs;; val concat : string list -> string = <fun>

That is, once `fold`

is available, their implementation becomes very
concise, which lets significantly less opportunities to make mistakes!

## Conclusion

`fold`

is basically a general way to perform an *iterative
computation*, like we would do with a loop: we put an initial value in
a accumulator variable, then we consider successively the elements of
the list by updating the variable with its previous value combined
with the next element in the list. It is then *as expressive* as a
loop, but *a lot safer*, since we don't need to take care of the loop
nor handle the accumulator variable correctly.

Note that there are two "natural" ways to iterate over a list (from
left to right, or from right to left), and that is why the standard
library offers two functions, `List.fold_left`

and
`List.fold_right`

. As an exercice, try to figure out which one it is
that we wrote (beware, there's a trap).

Since a `fold`

function is a way to iterate over a collection, we
could write some for other collections like trees, graphs, sets, hash
tables and so on. But that's yet another story.

P.S. A call to `fold`

is hidden in this messy code. Will you find it?

open Gg;; open Vg;; let cut_outline path img = let area = `O { P.o with P.width = 0.001 } in I.cut ~area path img ;; val cut_outline : Vg.path -> Vg.image -> Vg.image = <fun> let quadrilateral a b c d p = p |> P.sub a |> P.line b |> P.line c |> P.line d |> P.close ;; val quadrilateral : Gg.p2 -> Gg.p2 -> Gg.p2 -> Gg.p2 -> Vg.path -> Vg.path = <fun> let nested_squares_path n = let init = ( V2.v (-. 0.5) (-. 0.5), V2.v 0.5 (-. 0.5), V2.v 0.5 0.5, V2.v (-. 0.5) 0.5 ) in let f _ (accu, (a, b, c, d)) = let a' = V2.( a + 0.1 * (d - a) ) in let b' = V2.( b + 0.1 * (a - b) ) in let c' = V2.( c + 0.1 * (b - c) ) in let d' = V2.( d + 0.1 * (c - d) ) in (accu |> quadrilateral a' b' c' d', (a', b', c', d')) in List.init 100 (fun x -> x) |> fold f (P.empty, init) |> fst ;; val nested_squares_path : 'a -> Vg.path = <fun> let nested_squares = cut_outline (nested_squares_path 100) (I.const Color.black) |> I.move (V2.v 0.5 0.5) ;; val nested_squares : Vg.image = <abstr> Scirep.Show.vg nested_squares;;

```
- : unit = ()
```