map

Now that we've seen lists, it's useful to be able to perform operations on entire lists of data, rather than one thing at a time.

The map function allows us to transform a list into another list. It takes two inputs:

• A function with signature X -> Y, i.e. a function that takes an input of type X and returns an input of type Y, and
• A list of elements of type X

and "maps" the function over each item in the input list, returning a list of elements of type Y.

map : (X -> Y), (listof X) -> (listof Y)

Example

Suppose we have our good old function, doubler, which takes a number and multiplies it by two.

; doubler : number -> number
; takes a number and doubles it
(define doubler
  (lambda (x) (* 2 x)))

Now imagine we have the following list of numbers:

(list 1 3 -2 0)

We want to take this list, double each element, and return the newly-doubled list. We could go through the list one element at a time, applying doubler to each item and adding the result to a new list:

(list (doubler 1)
      (doubler 3)
      (doubler -2)
      (doubler 0))

…but that’s a lot of work, and we'd have to write this out manually every time we're given a new list.

Enter map.

(map doubler (list 1 3 -2 0))
; (list 2 6 -4 0)

Let's break down what happens under the hood:

So we can see that calling (map f list-of-things) returns the result of transforming list-of-things by applying f to each element of the list.

Since map is calling the specified f on each item of the specified list, it's important that the input type of f matches the type of list-of-things. Otherwise, we wouldn't be able to evaluate (f list-item).

Example with structs

(define-struct person (name age))

(define CONTACTS (list (make-person "Sarah" 20)
                       (make-person "Ian" 99)
                       (make-person "Bob" 14)
                       (make-person "Joe" 15)))

; age-one-year : person -> person
; returns a new person one year older
(define age-one-year
  (lambda (p)
    (make-person (person-name p)
                 (+ (person-age p) 1))))

(map age-one-year CONTACTS)
; (list (make-person "Sarah" 21)
;       (make-person "Ian" 100)
;       (make-person "Bob" 15)
;       (make-person "Joe" 16))

Example with strings

Consider the following helper function, append-obama, which appends "obama" to the end of an input string (very useful for thanking Obama):

; append-obama : string -> string
; appends "obama" to the end of a string
(define (append-obama str)
  (string-append str "obama"))

Given this helper, suppose we want to produce a list of thank-yous to Obama. We can easily accomplish this using map, like so:

(map append-obama (list "thanks" "thank you" "thx"))

which returns

(list "thanksobama" "thank youobama" "thxobama")

which is the same thing as

(list (append-obama "thanksobama")
      (append-obama "thank youobama")
      (append-obama "thxobama"))