Filter
Top Products
36 CHAPTER 4. EFFECTIVE CAML
#let sum l = itlist (prefix +) l 0;;
It is easy to modify this function to form a product rather than a sum:
#let prod l = itlist (prefix *) l 1;;
Many useful list operations can be implemented in this way. For example here
is a function to filter out only those elements of a list satisfying a predicate:
#let filter p l = itlist (fun x s -> if p x then x::s else s) l [];;
filter : (’a -> bool) -> ’a list -> ’a list = <fun>
#filter (fun x -> x mod 2 = 0) [1;6;4;9;5;7;3;2];;
it : int list = [6; 4; 2]
Here are functions to find whether either all or some of the elements of a list satisfy
a predicate:
#let forall p l = itlist (fun h a -> p(h) & a) l true;;
forall : (’a -> bool) -> ’a list -> bool = <fun>
#let exists p l = itlist (fun h a -> p(h) or a) l false;;
exists : (’a -> bool) -> ’a list -> bool = <fun>
#forall (fun x -> x < 3) [1;2];;
it : bool = true
#forall (fun x -> x < 3) [1;2;3];;
it : bool = false
and here are alternative versions of old favourites length, append and map:
#let length l = itlist (fun x s -> s + 1) l 0;;
length : ’a list -> int = <fun>
#let append l m = itlist (fun h t -> h::t) l m;;
append : ’a list -> ’a list -> ’a list = <fun>
#let map f l = itlist (fun x s -> (f x)::s) l [];;
map : (’a -> ’b) -> ’a list -> ’b list = <fun>
Some of these functions can themselves become useful combinators, and so on
upwards. For example, if we are interested in treating lists as sets, i.e. avoiding
duplicate elements, then many of the standard set operations can be expressed very
simply in terms of the combinators above:
#let mem x l = exists (fun y -> y = x) l;;
mem : ’a -> ’a list -> bool = <fun>
#let insert x l =
if mem x l then l else x::l;;
insert : ’a -> ’a list -> ’a list = <fun>
#let union l1 l2 = itlist insert l1 l2;;
union : ’a list -> ’a list -> ’a list = <fun>
#let setify l = union l [];;
setify : ’a list -> ’a list = <fun>
#let Union l = itlist union l [];;
Union : ’a list list -> ’a list = <fun>
#let intersect l1 l2 = filter (fun x -> mem x l2) l1;;
intersect : ’a list -> ’a list -> ’a list = <fun>
#let subtract l1 l2 = filter (fun x -> not mem x l2) l1;;
subtract : ’a list -> ’a list -> ’a list = <fun>
#let subset l1 l2 = forall (fun t -> mem t l2) l1;;
subset : ’a list -> ’a list -> bool = <fun>