Filter
Top Products
Chapter 4
Effective CAML
In this chapter, we discuss some of the techniques and tricks that CAML program-
mers can use to make programs more elegant and more efficient. We then go on
to discuss some additional imperative features that can be used when the purely
functional style seems inappropriate.
4.1 Useful combinators
The flexibility of higher order functions often means that one can write some very
useful little functions that can be re-used for a variety of related tasks. These are
often called combinators. It often turns out that these functions are so flexible that
practically anything can be implemented by plugging them together, rather than,
say, explicitly making a recursive definition. For example, a very useful combinator
for list operations, often called ‘itlist’ or ‘fold’, performs the following operation:
itlist f [x
1
; x
2
; .. . ;x
n
] b = f x
1
(f x
2
(f x
3
(· ·· (f x
n
b))))
A straightforward definition in CAML is:
#let rec itlist f =
fun [] b -> b
| (h::t) b -> f h (itlist f t b);;
itlist : (’a -> ’b -> ’b) -> ’a list -> ’b -> ’b = <fun>
Quite commonly, when defining a recursive function over lists, all one is doing
is repeatedly applying some operator in this manner. By using itlist with the
appropriate argument, one can implement such functions very easily without explicit
use of recursion. A typical use is a function to add all the elements of a list of
numbers:
#let sum l = itlist (fun x sum -> x + sum) l 0;;
sum : int list -> int = <fun>
#sum [1;2;3;4;5];;
it : int = 15
#sum [];;
it : int = 0
#sum [1;1;1;1];;
it : int = 4
Those especially keen on brevity might prefer to code sum as:
35