Higher Order Functions

Mapping, Filtering, and Folding

This section of the tutorial will deal with higher order list functions, specifically List.map, List.filter, and the grand-daddy of them all, List.fold_right. A higher order function can work with functions as data. This is one of the more distinguishing features of Ocaml.

Let's take a look at the definitions of these three functions:

# List.map;;
- : ('a -> 'b) -> 'a list -> 'b list = <fun>
# List.filter;;
- : ('a -> bool) -> 'a list -> 'a list =  <fun> >
# List.fold_right;;
- : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b =  <fun>

List.map

When you map across a list, you apply a function to every element in the list. This is why the first argument to List.map is ('a -> 'b) , which is a function that takes an argument of type 'a and returns an argument of type 'b. The second argument to List.map is a list of type 'a. The return value is a list of type 'b. Let's take a look at a quick and easy example:

# List.map (fun x -> x + 1) [1;2;3;4];;
- : int list = [2; 3; 4; 5]

As you can see, List.map is useful for list transformations. More specifically, you can make use of Ocaml's currying capabilities and write something such as rot13:

# let ints_of_chars = List.map (fun x -> (int_of_char x));; 
val ints_of_chars : char list -> int list = <fun>

# let chars_of_ints = List.map (fun x -> (char_of_int x));;
val chars_of_ints : int list -> char list = <fun>

# let subtract n = List.map (fun x -> (x - n));;
val subtract : int -> int list -> int list = <fun>

# let add n = List.map (fun x -> (x + n));;
val add : int -> int list -> int list = <fun>

# let remainder n = List.map (fun x -> (x mod n));;
val remainder : int -> int list -> int list = <fun>

# let rot_13 lst = 
  (chars_of_ints 
     (add 97 
	(remainder 26 
	   (add 13 
	      (subtract 97 
		 (ints_of_chars lst))))));;

val rot_13 : char list -> char list = <fun>
# rot_13 ['h'; 'e'; 'l'; 'l'; 'o'];;
- : char list = ['u'; 'r'; 'y'; 'y'; 'b']
# rot_13 ['u'; 'r'; 'y'; 'y'; 'b'];;
- : char list = ['h'; 'e'; 'l'; 'l'; 'o']

This example demonstrates mapping effectively. We essentially created five list 'mappers', and, by combining all of them, we can do something like rot13. However, this implementation is very slow because we map over the character list 6 times. It would be more efficient to do it in one fell swoop.

So, in summary, whenever you need to do any sort of list conversion, you should use List.map. However, what do you use if you want to remove items from a list? By far the best method of doing this is using List.filter.

List.filter

Let's take another look at its definition:

# List.filter;;
- : ('a -> bool) -> 'a list -> 'a list = <fun>

The first argument is a function that takes in one argument and returns either true or false. The second argument is a list of type 'a. The return value is a (usually trimmed) list of type 'a. Let's take a look at some quick examples:

# List.filter (fun x -> true) [1;2;3;4;5];;
- : int list = [1; 2; 3; 4; 5]
# List.filter (fun x -> false) [1;2;3;4;5];;
- : int list = []
# List.filter (fun x -> (x mod 2) = 0) [1;2;3;4;5];;
- : int list = [2; 4]