Making and Manipulating Homogeneous Lists

In building a complex drawing, one needs to construct and group a number of simpler drawings. For example, as we saw in one might create a drawing of an eye by grouping a variety of ellipses.

Of course, the kinds of drawings we make using the “drawings as values” are rarely so representational. More frequently, we will build abstract figures by composing a large number of simple images.

Let's start with a simple procedure, (drawing-centered-circle n), that takes a positive number as a parameter and creates a circle of radius n, centered at (n,n).

;;; Procedure:
;;;   drawing-centered-circle
;;; Parameters:
;;;   n, a positive number
;;; Purpose:
;;;   Create a circle of diameter n, centered at (n,n)
;;; Produces:
;;;   circle, a drawing
;;; Preconditions:
;;;   n > 0
;;; Postconditions:
;;;   [No additional]
(define drawing-centered-circle
  (lambda (n)
    (drawing-hshift
     (drawing-vshift
      (drawing-scale drawing-unit-circle n)
      n)
     n)))

(drawing-centered-circle 8)

(drawing-centered-circle 8)

Now, suppose we want to make a series of eight of these circles, using values of n from 1 to 8. We might write the following.

(define eight-circles
  (drawing-group (drawing-centered-circle 1)
                 (drawing-centered-circle 2)
                 (drawing-centered-circle 3)
                 (drawing-centered-circle 4)
                 (drawing-centered-circle 5)
                 (drawing-centered-circle 6)
                 (drawing-centered-circle 7)
                 (drawing-centered-circle 8)))

eight-circles

But that's a lot of code to write. And it's likely to be worse. Suppose we wanted to make more than eight circles (say, one hundred circles). It doesn't seem worth the effort, even with cutting and pasting. Since programming is supposed to ease the need for tedious, repetitive tasks, there must be something better.

Fortunately, there is. In this reading, we will consider Scheme's list data type, which is used to group values, as well as a variety of procedures to build and manipulate lists.

In Scheme, a list is an ordered collection of values. Once you've created a list, the Scheme interpreter shows lists in a fairly simple format:

For example, the Scheme interpreter would show a list of the numbers 2, 3, 5, 7 as (2 3 5 7), a list of strings giving the English names of those numbers as ("two" "three" "five" "seven"), and a list of symbols giving the English names of thos numbers as (two three five seven).

You may have noted something a bit strange about lists ... they look a lot like procedure calls. (Recall that a procedure call has an open parenthesis, a procedure name, a sequence of parameters separated by spaces, and a close parenthesis.) So, how do we know when we have a procedure call and when we have a list? It depends on the context. Typically, the interpreter assumes that things you type that start with open parentheses are procedure calls (or something similar) and the things that it types that start with open parentheses are lists.

There are a number of ways to create lists, but the easiest is the list procedure. This procedure takes as many parameters values you want to give it, and creates a list containing those values.

> (list 2 3 5 7)
(2 3 5 7)
> (list "two" "three" "five" "seven")
("two" "three" "five" "seven")
> (list 'two 'three 'five 'seven)
(two three five seven)

Another relatively simple way to make lists is the (make-list n val) procedure, which makes a list of n copies of val.

> (make-list 5 'hello)
(hello hello hello hello hello)
> (make-list 7 1)
(1 1 1 1 1 1 1)
> (make-list 3 "goodbye")
("goodbye" "goodbye" "goodbye")

Why would we want a list of multiple copies of the same value? We'll see why in a bit.

So, what can you do with lists once you've created them? Build other lists, of course. The first way we'll build lists from lists is with the (map proc lst) procedure, which creates a new list by applying the procedure proc to each element of the list lst.

For example, if we want a list of the squares of the first ten positive integers (and we're too lazy to compute them by hand), we can use map to apply the square procedure to each element of the list of the first ten positive integers.

> (map square (list 1 2 3 4 5 6 7 8 9 10))
(1 4 9 16 25 36 49 64 81 100)

We can also find out the square roots of those same ten numbers.

> (map sqrt (list 1 2 3 4 5 6 7 8 9 10))
(1 1.4142135623730951 1.7320508075688772 
 2 2.23606797749979 2.449489742783178 
 2.6457513110645907 2.8284271247461903 3 

We can check those results by squaring them again.

> (map square (map sqrt (list 1 2 3 4 5 6 7 8 9 10)))
(1 2.0000000000000004 2.9999999999999996 
 4 5.000000000000001 5.999999999999999 
 7.000000000000001 8.000000000000002 9 
 10.000000000000002)

We can also apply a user-defined function to each value in the list.

> (define f (lambda (x) (+ 1 (* 2 x))))
> (map f (list 1 2 3 4 5 6 7 8 9 10))
(3 5 7 9 11 13 15 17 19 21)

What does any of this have to do with building complex drawings? Well, the drawings as values library includes a convenient procedure, (drawing-compose list-of-drawings), which, given a list of drawings, builds a new drawing by combining them together.

That means we can return to our original problem of building eight circles of radii 1, 2, 3, 4, 5, 6, 7, and 8 as follows.

In Scheme,

> (define eight-circles 
    (drawing-compose (map drawing-centered-circle (list 1 2 3 4 5 6 7 8))))

If that's all we care about in our drawing, we can build an image with drawing->image. We can also use that drawing in other ways (e.g., shift it, add a shadow).

Because of the power of map, it is easy to make some interesting variations. For example, instead of the numbers from 1 to 8, we can use the squares of those numbers to get a different effect.

> (define another-eight-circles
    (drawing-compose (map drawing-centered-circle
                        (map square (list 1 2 3 4 5 6 7 8)))))

The instructions above are much more concise than our original instructions for building a collection of eight circles. But it will still take a bit of effort to get one hundred circles. Does Scheme provide other tools that will help? Of course!

The (iota n) procedure creates a list of all the non-negative integers less than n, arranged in increasing order.

> (iota 5)
(0 1 2 3 4)
> (map increment (iota 5))
(1 2 3 4 5)

As this example suggests, when you want the numbers to start at 1 and go through n, you simply need to increment each value in the original list.

We now have the tools to create a picture of 100 circles.

First, we build the numbers from 1 to 100.

> (define nums-to-100 (map increment (iota 100)))

Next, we build circles from each of those numbers.

> (define circles (map drawing-centered-circle nums-to-100))

We turn that list of circles into a drawing.

> (define one-hundred-circles (drawing-compose circles))

And, optionally, we render the drawing.

> (image-show (drawing->image one-hundred-circles 200 100))

Of course, we need not use all those intermediate definitions. We could, just as easily, write

> (define one-hundred-circles
    (drawing-compose (map drawing-centered-circle
                          (map increment (iota 100)))))

one-hundred-circles

We also have the tools to make other interesting combinations of circles, such as circles shifted by 1, 4, 9, 16, ..., 100, or by 10, 20, 30, ..., 100.

> (define quadratic-circles
    (drawing-compose (map drawing-centered-circle
                          (map square (map increment (iota 10))))))
> (define times10 (lambda (x) (* 10 x)))
> (define circles-by-ten
    (drawing-compose (map drawing-centered-circle
                          (map times10 (map increment (iota 10))))))

quadratic-circles

circles-by-ten

How do these work? Let's look at the lists the subexpressions compute.

> (iota 10)
(0 1 2 3 4 5 6 7 8 9)
> (map increment (iota 10))
(1 2 3 4 5 6 7 8 9 10)
> (map square (map increment (iota 10)))
(1 4 9 16 25 36 49 64 81 100)
> (map times10 (map increment (iota 10)))
(10 20 30 40 50 60 70 80 90 100)

Why don't we bother to name the intermediate lists, rather than doing such deep nesting? Because we're only planning to use these lists once (as we experiment with building the drawing) and we try to avoid naming things we may not need again. (Okay, sometimes it's just that we're too lazy to come up with a name.

These drawings, while potentially interesting, are clearly getting just a bit too similar. One problem we're encountering is that each individual circle depends on just one number, and then we use that number for the horizontal shift, the vertical shift, and the diameter. We'd really like to be able to set the three parameters separately for each drawing.

Fortunately, the map procedure allows you to provide not just one list, but as many as you'd like. It then builds a new list by applying the procedure to the corresponding elements of all the lists. For example,

> (map * (list 1 2 3) (list 4 5 6))
(4 10 18)
> (map + (list 1 2) (list 3 4) (list 5 6))
(9 12)

> (map list (iota 10) (map increment (iota 10)) (map square (iota 10)))
((0 1 0) (1 2 1) (2 3 4) (3 4 9) (4 5 16) (5 6 25) (6 7 36) (7 8 49) (8 9 64) (9 10 81))

> (define first-names (list "Addison" "Bailey" "Casey" "Devon" "Emerson"))
> (define last-names (list "Smith" "Jones" "Smyth" "Johnson" "Doe"))
> (map string-append first-names (make-list 5 " ") last-names)
("Addison Smith" "Bailey Jones" "Casey Smyth" "Devon Johnson" "Emerson Doe")
> (map string-append last-names (make-list 5 ", ") first-names)
("Smith, Addison" "Jones, Bailey" "Smyth, Casey" "Johnson, Devon" "Doe, Emerson")

How is that helpful? Well, we can start with a drawing of our choice, use make-list to make multiple copies, and use map with some combination of the drawing procedures (e.g., drawing-hshift or drawing-scale).

Here's a list of circles, all of diameter five, with quadratic spacing along the horizontal axis.

(define basic-circle
  (drawing-vshift (drawing-scale drawing-unit-circle 5) 50))

(define circles01
  (map drawing-hshift (make-list 10 basic-circle)
                      (map square (iota 10))))

(drawing-compose circles01)

Here's the same set of circles, spaced out a little bit more along the vertical axis.

(define circles02
  (map drawing-vshift
       (map drawing-hshift (make-list 10 (drawing-scale drawing-unit-circle 5))
                           (map square (iota 10)))
       (map times10 (iota 10))))

(drawing-compose circles02)

For those who don't like such deep nesting, here's a version that shows the step-by-step breakdown.

(define circles02-vshifts (map times10 (iota 10)))
(define circles02-hshifts (map square (iota 10)))

(define circles02
  (map drawing-vshift
       (map drawing-hshift (make-list 10 (drawing-scale drawing-unit-circle 5))
                           circles02-hshifts)
       circles02-vshifts))

Here's a set of one hundred circles, spaced equally horizontally, with vertical shift varying from 0 to 19.

(define mod20
  (lambda (y) (mod y 20)))

(define circles03
  (map drawing-vshift 
       (map drawing-hshift
            (make-list 100 (drawing-scale drawing-unit-circle 5))
	    (iota 100))
       (map mod20 (iota 100))))

(drawing-compose circles03)

What's happening here? The mod procedure takes our list of integers between 0 and 99, and makes them wrap around to 0 every twenty steps.

> (map mod20 (iota 100))
(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19)

We can see the effect a bit better if we space things out.

(define mod10
  (lambda (y) (mod y 10)))
(define times5
  (lambda (x) (* 5 x)))
(define circles04
  (map drawing-vshift 
       (map drawing-hshift
            (make-list 40 (drawing-scale drawing-unit-circle 5))
	    (map times5 (iota 40)))
       (map times10 (map mod10 (iota 40)))))

(drawing-compose circles04)

We can use the same technique to modify the radii of the circles.

(define mod5
  (lambda (y) (mod y 5)))

(define circles05
  (map drawing-vshift 
       (map drawing-hshift
            (map drawing-scale
                 (make-list 40 drawing-unit-circle)
		 (map increment (map mod5 (iota 40))))
	    (map times5 (iota 40)))
       (map times10 (map mod10 (iota 40)))))

(drawing-compose circles05)

(define mod7
  (lambda (y) (mod y 7)))

(define circles06
  (map drawing-vshift 
       (map drawing-hshift
            (map drawing-scale
                 (make-list 40 drawing-unit-circle)
		 (map increment (map mod7 (iota 40))))
	    (map times5 (iota 40)))
       (map times10 (map mod10 (iota 40)))))

(drawing-compose circles06)

This last one is complex enough that it's worth looking at the components. Note that we start by scaling the circles (using a computed list of values) and then horizontally and vertically shift those circles. Let's see what the lists we use for scaling, horizontal shifting, and vertical shifting look like.

> (map increment (map mod7 (iota 40)))
(1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 .....
> (map times5 (iota 40))
(0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 1 .....
> (map times10 (map mod10 (iota 40)))
(0 10 20 30 40 50 60 70 80 90 0 10 20 30 40 50 60 70 80 90 0 10 20 30 40 50 60 7 .....

Because the cycle of the radius and the cycle of the vertical shifts are of different lengths, we get somewhat more complex variation in circles06 than in circles05. We can also get an interesting effect by combining the draw drawings.

(define combined-circles
  (drawing-group (drawing-compose circles05)
                 (drawing-hshift (drawing-compose circles06) 10)))

combined-circles

There are a wide variety of procedures that you can use to manipulate lists. Here are some of the ones you may find useful as you use lists to build compound drawings.

The (reverse lst) procedure creates a new list, consisting of the elements of lst, but in the opposite order.

> (reverse (iota 10))
(9 8 7 6 5 4 3 2 1 0)
> (reverse (list 'alpha 'beta 'gamma 'delta 'epsilon))
(epsilon delta gamma beta alpha)

The (append lst1 lst2) builds a new list by joining two lists together.

> (append (iota 5) (iota 5))
(0 1 2 3 4 0 1 2 3 4)
> (append (make-list 3 'alpha) (make-list 4 'beta))
(alpha alpha alpha beta beta beta beta)

The (list-take lst n) procedure builds a new list consisting of the first n elements of lst.

> (list-take (reverse (iota 10)) 7)
(9 8 7 6 5 4 3)

The (list-drop lst n) procedure builds a new list consisting of all but the first n elements of lst.

> (list-drop (iota 10) 3)
(3 4 5 6 7 8 9)

Why do two of these procedures (list-take and list-drop) include “list” in their name and two of them (reverse and append) not? Well ... the ones without “list” are part of standard Scheme, and were added to the language when lists were the only collection type. The other two were added as part of MediaScript, and we make it a point to name our procedures with the type they work with. (There are variants of Scheme that simply provide take and drop, often with the parameters in the opposite order.