Mapping Operations

Summary

We investigate a particular form of decomposition relevant in computing: transformations over a collection of values are really transformations of the individual elements of the collection.

Prerequisites

List Basics.

Imagine representing the collection of yearly salaries found at a startup using a simple list, for example:

(define salaries (list 100000 100000 50000 75000 500000))

And now imagine computing everyone’s updated salary after a standard cost-of-living ajustment (COLA). We might decompose this problem into the problem of computing one person’s updated salary. Let’s take the first person whom makes 100000 (units deliberately unspecified) as an example. The Social Security COLA for 2020 was %1.6, so we can calculate the updated salary using arithmetic:

> (+ 100000 (* 100000 0.016))
101600.0

And we can abstract this into a function that computes the updated salary when given a salary:

;;; Procedure:
;;;   compute-cola-salary
;;; Parameters:
;;;   salary, a Number
;;; Purpose:
;;;   Computes the cost-of-living-adjusted salary for an individual.
;;; Produces:
;;;   the updated salary, a Number
;;; Preconditions:
;;;   salary is a valid monetary amount (i.e., non-negative)
;;; Postconditions:
;;;   (compute-cola salary salary) is the COLA salary.
(define compute-cola-salary
  (lambda (salary) (+ salary (* salary 0.016))))

Good! We can now calculate the updated salary for any person. However, how do we do this for a collection of salaries represented as a list?

Note that the calculation of each salary is independent of the other salaries. That is, someone’s adjusted salary only depends on their salary and not others. In this situation, we simply want to apply our solution for a single person, compute-cola-salary, to every element of the list. We say that we want to lift the function compute-cola-salary from operating on a single salary to a list of salaries.

In Racket, we realize the behavior of lifting a function to a list of values with the map function:

> (map compute-cola-salary salaries)
'(101600.0
  1016000.0
  50800.0
  76200.0
  5080000.0)

The Map Function

map is a powerful function! It allows to concisely describe how to transform the values of a list in terms of an operation over a single element of the list. Let’s break down how you use map.

map itself is a function of two arguments as seen in our above example.

• The first argument is a function that transforms a single element of the list. By “transform”, we mean the function:

  • Takes as an input an element of the list.
  • Produces as an output the result of transforming that element.

  In our above example, compute-cola-salary is a function that transforms an old salary into a new, adjusted salary.

• The second argument is a list that contains the elements that we wish to transform.

Any transformation function over salaries can be passed in to our call to map, for example, the startup might have went public so everyone gets their salary doubled:

> (define double-salary (lambda (salary) (* salary 2)))
> (map double-salary salaries)
'(200000
  200000
  100000
  150000
  1000000)

The startup might have hit a downturn and needs to reduce their salaries:

> (define downsize (lambda (salary) (/ salary 2)))
> (map downsize salaries)
'(50000
  50000
  25000
  37500
  250000)

Or worse yet, the downturn might be so bad that the startup needs to do the right thing and let go of its higher-earning employees to stay under budget:

> (define should-keep (lambda (salary) (< salary 75000)))
> (map should-keep salaries)
'(#f #f #t #f #f)

This last example shows off a new type that we haven’t seen before, the boolean type, which captures values that are either true or false. In Racket, we write true as #t and false as #f. (Note that this is different from the single characters ‘t’ and ‘f’ which are written as #\t and #\f, respectively.) The < operator behaves like you expect—it is checking whether the given salary is less than 75000. Therefore, the resulting list contains a #t entry if the salary is less than 75000 and #f otherwise! We’ll have more to say about using booleans to control the flow of our programs next week.

Map as Transforming Collections of Data

This last example alludes to the idea that map isn’t constrained to keep the type of the elements of the resulting list the same as the old list. Indeed, the power of the map is we can transform the list in arbitrary ways as long as those transformations are independent between list elements. As long as we can recognize the “collection” being transformed in our problem, we can write solutions in surprisingly elegant ways.

As an example, consider the problem of drawing the following image:

Using decomposition, we might recognize this image as a bunch of green circles of different sizes. We could write a function that captures a single green circle parameterized by size:

(define green-circle
  (lambda (size) (circle size 'solid "green")))

And we can use green-circle to better capture the structure of the image in code:

> (beside (green-circle 20)
          (green-circle 40)
          (green-circle 60)
          (green-circle 40)
          (green-circle 20))

But look at that redundancy! Calling green-circle many times is undesirable: it takes time and effort to read and write the code. Furthermore, the “repetitive” nature of the image isn’t truly captured in the code. This keeps us from generalizing the function further, e.g., varying the numbers of green-circles in the figure.

However, if we instead decompose the problem as a transformation over lists instead, we’ll arrive at a better solution. But where is the list in this code? While there isn’t a list anywhere in the code for us to immediately map over, we do note that the image can be thought of as a collection of circles.

With this in mind, we can decompose the problem of generating a collection of circles into creating a single circle. The way we do this is with green-circle, passing in its size. The size is therefore the element we are transforming! We’re transforming a size into a circle by way of the green-circle function. We can then transform a collection of sizes into a collection of circles by lifting green-circle using map:

> (define circles (map green-circle (list 20 40 60 40 20)))
> circles

(Note: I can’t easily reproduce the layout of the images inlined with the text in HTML, so the output from the last map call is a screenshot of the output on my own machine.)

We aren’t done yet! This isn’t a single image composed of a bunch of green circles. This is a list of green circles of different sizes (note the (list ... ) surrounding the circles).

As with the original version of the code, we need to use beside to combine the circles. However, if we simply pass this expression to beside, we get an error:

> (beside circles)
 .../lang/prim.rkt:24:44: beside: arity mismatch;
 the expected number of arguments does not match the given number
   expected: at least 2
    given: 1
    arguments...:

Why does this error occur? Let’s think carefully about the types of the values involved:

• beside is a function that takes a collection of images, one per argument, e.g., (beside image1 image2 image3).
• circles is defined to be (map green-circle (list 20 40 60 40 20)) which is a list of images.

Finally, consider the complete expression (besides circles). Each argument to besides should be a single image but circles is a list of images instead. That’s where our error arises!

Ultimately, we have to someone pass in each image in the list circles to each argument position of besides. How do we do this? It turns out we have to employ an additional standard library function of Racket to do this, apply:

> (apply beside circles)

More generally, apply is a helpful standard library function when working with lists of arguments. apply takes two arguments:

• A function to run or apply on a collection of arguments.
• The collection of arguments to apply to the function, stored in a list.

As a simpler example of apply, consider the simple (+) function which can take any number of arguments:

> (+ 1 2 3 4 5)
15

While (+) takes any number of arguments, it cannot take a single list as an argument:

> (+ (list 1 2 3 4 5))
+: contract violation
  expected: number?
  given: '(1 2 3 4 5)

To pass this list of numbers to (+), we can use the apply function:

> (apply + (list 1 2 3 4 5))
15

Summary

So let’s summarize the image code we’ve written:

(define green-circle
  (lambda (size) (circle size 'solid "green")))

(define circles
  (map green-circle (list 20 40 60 40 20)))

(define circles-besides
  (apply beside circles))

> circles-besides

We’ve decomposed the problem of drawing the circles not as a series of repeated calls to green-circles but as a collection that is the result of transforming the sizes of the circles into green circles. While this interpretation may have come less naturally to you, I would argue that once you understand transformations with map that this is a more readable and concise solution to the problem.

As a final note, I’ll mention that it is more flexible, too. For example, there’s nothing special about the fact that we wanted the circles besides each other. The following modified code leverages our abstractions to get a different effect with minimal results:

> (apply above circles)

This is the power of decomposition in action! In particular, if we use appropriate abstractions, we can create highly reusable code that both captures our intent but can be used in other contexts with minimal modification.

Self-Check (Differences) (‡)

Write a function decrement that takes an integer as input and returns an integer one less than the input.

Now use decrement and map to write an expression that decrements the contents of the following list three times:

(define example-list (list 10 20 30 40 50))