Fold vs. Recursive vs. Library
We've now seen three different ways for writing functions that manipulate lists:
directly as a recursive function that pattern matches against the empty list and
against cons, using
fold functions, and using other library functions.
Let's try using each of those ways to solve a problem, so that we can
appreciate them better.
Consider writing a function
lst_and: bool list -> bool, such that
lst_and [a1; ...; an] returns whether all elements of the list are
true. That is, it evaluates the same as
a1 && a2 && ... && an.
When applied to an empty list, it evaluates to
Here are three possible ways of writing such a function. We give each way a slightly different function name for clarity.
let rec lst_and_rec = function |  -> true | h::t -> h && lst_and_rec t let lst_and_fold = List.fold_left (fun acc elt -> acc && elt) true let lst_and_lib = List.for_all (fun x -> x)
The worst-case running time of all three functions is linear in the
length of the list. But the first function,
has the advantage that it need not process
the entire list: it will immediately return
false the first time
they discover a
false element in the list. The second function,
lst_and_fold, will always process every element of the list.
As for the third function
lst_and_lib, according to its
(p a1) && (p a2) && ... && (p an).
lst_and_rec it need not process every element.