Mastering Functional Programming with OCaml and Haskell/

...

/

The map Function

The map Function

Understand the higher-order map function and see its applications on lists, trees, options, abstract domains, and contexts.

We'll cover the following...

The map function is one of the most popular abstractions in the functional programming paradigm. It is best known for mapping the elements of a list to new elements. Due to its usefulness, map has found its way into most mainstream programming languages, such as JavaScript, Java, and Python.

The map function on lists

One way of looking at map on lists is that it represents a general method of computation on lists. First, let’s write a square_list function that squares all elements in a list to see what that pattern is.

Press + to interact
(** [print_int_list] prints an integer list [l] to the console. *)
let print_int_list l = print_string ("[" ^ (String.concat "; " (List.map string_of_int l)) ^ "]")
(** [square_list] returns a list whose elements are the square of the elements of an input list [l]. *)
let rec square_list l = match l with
                        | [] -> []
                        | hd :: tl -> (hd * hd) :: square_list tl
(** Printing the result of 'square_list [1; 2; 3]' to the console. *)
let _ = print_int_list (square_list [1; 2; 3])

Let’s write another function called cube_list that turns the elements of a list into their cube.

Press + to interact
(** [print_int_list] prints an integer list [l] to the console. *)
let print_int_list l = print_string ("[" ^ (String.concat "; " (List.map string_of_int l)) ^ "]")
(** [cube_list] returns a list whose elements are the cube the of elements of an input list [l]. *)
let rec cube_list l = match l with
                      | [] -> []
                      | hd :: tl -> (hd * hd * hd) :: cube_list tl
(** Printing the result of 'cube_list [1; 2; 3]' to the console. *)
let _ = print_int_list (cube_list [1; 2; 3])

The implementations of square_list and cube_list are strikingly similar. The differences between these functions lie in their last lines, which compute the head of the output list from the head of the input list, hd * hd vs. hd * hd * hd. Other than that, the shape of the functions looks identical.

As we have seen multiple times in the course, this kind of common shape is almost always an opportunity to climb up the abstraction hierarchy. We can factor out the common pattern into a higher-order map function that takes an f function and a list as input. It then applies f uniformly to all list elements and produces a new list containing the resulting elements. The two functions, square_list and cube_list, become particular cases of map.

Press + to interact
(** [print_int_list] prints an integer list [l] to the console. *)
let print_int_list l = print_string ("[" ^ (String.concat "; " (List.map string_of_int l)) ^ "]")
(** [map f l] applies a function [f] to all elements in a list [l]. *)
let rec map f l = match l with
                  | [] -> []
                  | hd :: tl -> (f hd) :: map f tl;;
(** [square_list] is a function that squares elements of a list. *)
let square_list = map (fun x -> x * x)
(** [cube_list] is a function that turns elements of a list into their cube. *)
let cube_list = map (fun x -> x * x * x)
(** Printing the result of 'square_list [1; 2; 3]' and 'cube_list [1; 2; 3]' separated by a new line to the console. *)
let _ = print_int_list (square_list [1; 2; 3]);
        print_newline ();
        print_int_list (cube_list [1; 2; 3]);

The following diagram illustrates this abstraction process:

What makes map such a powerful abstraction is that it allows us to treat the transformation of a sequence of data as a high-level concept. With map, we focus on what transformation is rather than what the transformation step looks like.

Another excellent way to understand ...