Let's say you want every even element from a list of integer. We can right a function that does this:
let rec evens = function
| [] -> []
| h :: t -> begin
if h mod 2 = 0
then h :: evens t
else evens t
end
let rec odds = function
| [] -> []
| h :: t -> begin
if h mod 2 = 1
then h :: odds t
else odds t
end
val evens : int list -> int list = <fun>
val odds : int list -> int list = <fun>
Look how similar our code is! Let's abstract out the common elements
Here, p is a predicate, a function that returns a bool.
let rec filter p = function
| [] -> []
| h :: t -> if p h then h :: filter p t else filter p t
val filter : ('a -> bool) -> 'a list -> 'a list = <fun>
Now let's implement our even and odd functions in terms of filter!
let even x = x mod 2 == 0
let odd x = x mod 2 == 1
let evens' = filter even
let odds' = filter odd
val even : int -> bool = <fun>
val odd : int -> bool = <fun>
val evens' : int list -> int list = <fun>
val odds' : int list -> int list = <fun>
let nums = [1;2;3;4;5;6;7;8;9;10];;
evens nums;;
evens' nums;;
odds nums;;
odds' nums;;
val nums : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
- : int list = [2; 4; 6; 8; 10]
- : int list = [2; 4; 6; 8; 10]
- : int list = [1; 3; 5; 7; 9]
- : int list = [1; 3; 5; 7; 9]
Filter (as implemented) is not tail-recursive. Let's implement a tail recursive version of filter!
let rec filter' p lst =
let rec filter_aux p acc = function
| [] -> List.rev acc (* we need to reverse the accumulator, because we're processing backwards*)
| h :: t -> filter_aux p (if p h then h :: acc else acc) t
in filter_aux p [] lst
val filter' : ('a -> bool) -> 'a list -> 'a list = <fun>
let odds'' = filter' odd;;
let evens'' = filter' even;;
odds'' nums;;
evens'' nums;;
val odds'' : int list -> int list = <fun>
val evens'' : int list -> int list = <fun>
- : int list = [1; 3; 5; 7; 9]
- : int list = [2; 4; 6; 8; 10]