Mastering Functional Programming with OCaml and Haskell/

...

/

The fold Function

The fold Function

Learn the higher-order function fold and see how it can be defined on lists, tree structures, and other algebraic datatypes.

We'll cover the following...

The fold function on lists

Often, we need to combine list elements into a single value. For example, given a list, we might want to calculate the sum or the product of its elements. Such a computation pattern can be realized in the functional paradigm through a powerful function abstraction called fold.

Let’s define a function, sum_list, to calculate the sum of all numbers from a list of integers.

Press + to interact
(** [sum_list l] equals the sum of all integer elements in a list [l]. *)
let rec sum_list l = match l with
  | [] ->  0
  | hd :: tl -> hd + sum_list tl
(** Printing the result of 'sum_list [1; 2; 3; 4]' to the console *)
let _ = print_int (sum_list [1; 2; 3; 4])

Next, let’s define another function, prod_list, to return the product of all numbers from a list.

Press + to interact
(** [prod_list l] equals the sum of all integer elements in a list [l]. *)
let rec prod_list l = match l with
  | [] ->  1
  | hd :: tl -> hd * prod_list tl
(** Printing the result of 'prod_list [1; 2; 3; 4]' to the console *)
let _ = print_int (prod_list [1; 2; 3; 4])

The sum_list and prod_list functions follow the same computation pattern.

  • In case of an empty list [], return an initial value, 0 for sum_list, and 1 for prod_list.
  • For a hd :: tl list, apply a binary function f to hd, and the result for recursively processed tl. The function is addition + for sum_list, and multiplication * for prod_list.

This computation pattern is precisely what fold_right captures. We’ll see in a minute why it is called fold_right. There is another fold version called fold_left, but we’ll cover it later.

let rec fold_right f init l  = match l with
  | [] ->  init
  | hd :: tl -> f hd (fold_right f init tl)

Here, f is the function used to combine the list elements, init is the initial value. The last argument l is the input list.

This function is called fold_right because the way it works is visually similar to how we fold ...