17 Implementing Map

Lets look at how map could be written by looking at how some other functions can be applied to manipulate lists.

Let's add one to every element in a list:

let rec add1 = function
	| [] -> []
	| h :: t -> (h + 1) :: add1 t;;

val add1 : int list -> int list = <fun>

let naturals = [1; 2; 3; 4; 5; 6];;

val naturals : int list = [1; 2; 3; 4; 5; 6]

Now let's test our function:

add1 naturals;;

- : int list = [2; 3; 4; 5; 6; 7]

Perfect!

What if we wanted to concatenate 3110 to each item in a list

let rec concat3110 = function
	| [] -> []
	| h :: t -> (h ^ "3110") :: concat3110 t

val concat3110 : string list -> string list = <fun>

let strings = ["hello"; "world"; ]

val strings : string list = ["hello"; "world"]

concat3110 strings;;

- : string list = ["hello3110"; "world3110"]

Look at the implementation of these two functions. There's a lot repeated code, let's factor it out:

let rec transform = function
    | [] -> []
    | h :: t -> ?? :: transform t

What do we do with the ??? Let's pass a function to transform the element

let rec transform f = function
	| [] -> []
	| h :: t -> f h :: transform f t;;

val transform : ('a -> 'b) -> 'a list -> 'b list = <fun>

Now we can implement our add1 and concat3110 functions with transform

let add1' = transform (fun x -> x + 1);;
let concat3110' = transform (fun x -> x ^ "3110");;

val add1' : int list -> int list = <fun>

val concat3110' : string list -> string list = <fun>

add1 naturals;;
concat3110 strings;;

- : int list = [2; 3; 4; 5; 6; 7]

- : string list = ["hello3110"; "world3110"]

Look at that!

Guess what. Transform is actually map! This is the implementation of List.map in the standard library:

source

let rec map f = function
    [] -> []
  | a::l -> let r = f a in r :: map f l

Let's look at the type of map:

List.map;;

- : ('a -> 'b) -> 'a list -> 'b list = <fun>

It takes a function of type ('a -> 'b), because you don't need to return a list of the same type!

let string_list_of_int_list = List.map string_of_int;;

val string_list_of_int_list : int list -> string list = <fun>

string_list_of_int_list naturals;;

- : string list = ["1"; "2"; "3"; "4"; "5"; "6"]

Map takes that function, and an 'a list, and applies the function to each of them, then returns a 'b list.

What we just did here was apply the abstraction principle: Factor out recurring code patterns. Don't duplicate them.