Search⌘ K
Home
Courses
Mastering Functional Programming with OCaml and Haskell

The fold Function

Explore the fold function to combine elements of lists, trees, and other data types into single outcomes. Understand fold_right and fold_left, and see how fold abstracts common computations like sum, product, any, and all. Discover fold applications on binary trees, options, and natural numbers to efficiently process recursive data structures.

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.

OCaml
(** [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.

OCaml
(** [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 clothes. In particular, we fold the list from right to ...