Laboratory: Exploring Lists

a. Using the cons procedure, build a one-element list that contains the value "red". The result of your call should be '("red").

b. Use the cons procedure to build a list of the value 5 followed by the value "red". The result of your call should be '(5 "red"). Note that you will need to call cons twice to build this list.

c. Call the cons procedure to build a list of the value 2, followed by the value 5, followed by "red". The result of your call should be '(2 5 "red"). Note that you will need to call cons three times to build this list.

d. Build the same list as in step c, using list rather than cons.

Consider the following list definition, which you can enter in the interactions pane of your work window.

(define letters (list 'a 'b 'c 'd 'e 'f 'g 'h 'i))

a. What do you expect the result of (car letters) to be? Check your answer experimentally.

b. What do you expect the result of (cdr letters) to be? Check your answer experimentally.

c. What do you expect the result of (car (cdr letters)) to be? Check your answer experimentally.

d. What do you expect the result of (cdr (cdr letters)) to be? Check your answer experimentally.

e. What do you expect the result of (cdr (car letters)) to be? Check your answer experimentally.

f. Write an expression using car and cdr that extracts element 5 of letters. (That is, your expression should extract the f.)

As you may recall, the cons procedure takes two parameters, a value and a list. It builds a new list by prepending the value to another list. However, it is also possible to apply cons to two non-list values. (You should not regularly do so at this point in your career, but some accidentally apply cons in this different way, so we want you to see what happens.)

Consider the following:

(define one-two-0 (cons 1 2))
(define one-two-1 (list 1 2))
(define one-two-2 (cons 1 (cons 2 null)))

a. Enter these definitions in the interactions pane of your work window and then ask for the values of one-two-0, one-two-1, and one-two-2. Explain how they are and are not similar.

b. What do you expect to have happen when you apply the list? predicate to each value? Check your answer experimentally.

c. What do you expect to have happen when you call reverse on each? Check your answer experimentally.

d. What do you expect to have happen if you try to get the car and the cdr of each of these values? Check your answer experimentally.

e. What do you expect to have happen if you append the list '(3 4) to each of these values, as in the following example?

> (append one-two-0 (list 3 4))
?
> (append one-two-1 (list 3 4))
?
> (append one-two-2 (list 3 4))
?

Check your answer experimentally.

f. What do you expect to have happen if you append each of these values to the list '(0 0), as in the following example?

> (append (list 0 0) one-two-0)
?
> (append (list 0 0) one-two-1)
?
> (append (list 0 0) one-two-2)
?

If you are confused by any of the results, please look at the notes on this problem.

In the reading, we implemented simple shapes as heterogeneous lists with the kind of shape first, the color second, the x and y coordinates third and fourth, and the size fifth. The “drawings as values” model uses the same strategy, although with more elements.

> drawing-unit-circle
'(drawing ellipse 0 "" -0.5 -0.5 1 1)
> drawing-unit-square
'(drawing rectangle 0 "" -0.5 -0.5 1 1)
> (hscale-drawing 10 (vscale-drawing 20 drawing-unit-circle))
'(drawing ellipse 0 "" -10.0 -5.0 20 10)
> (hshift-drawing 30 (vshift-drawing 40 drawing-unit-square))
'(drawing rectangle 0 "" 39.5 29.5 1 1)
> (recolor-drawing "red" drawing-unit-circle)
'(drawing ellipse 16711680 "" -0.5 -0.5 1 1)
> (recolor-drawing  "yellow" drawing-unit-circle)
'(drawing ellipse 16776960 "" -0.5 -0.5 1 1)

As this example suggests, drawings of shapes are currently represented as eight element lists. The element 0 is always the symbol drawing. The element 1 is either the symbol ellipse or the symbol rectangle. Element 2 is the color (in the unreadable integer-encoded RGB format). Element 3 is the empty string and never seems to change. (In fact, it's something we used in an older implementation of drawings, and has just refused to leave.) Element 4 is the left edge, element 5 is the top edge, element 6 is the width, and element 7 is the height.

As you may have discovered earlier, it's dangerous to rely on the internal representation when you write procedures. However, let's suppose for the moment that you were willing to do so.

Write and test a procedure, (drawing-make-ellipse left top width height), that creates a new, filled, black ellipse with the specified edges and size. Rather than starting with the unit circle and scaling and shifting it, your procedure should build the list that represents the drawing directly.

For example, the following should render a 20x10 black ellipse with a left edge of 5 and a top edge of 15.

> (image-show (drawing->image (drawing-make-ellipse 5 15 20 10) 50 50))

In the reading, we saw that we could convert our simple diamond shapes to squares by building new lists that replace the symbol diamond with the symbol square. We might do something similar with the “drawings as values” model.

Write a procedure, (rectangularize drawing), that checks if drawing is an ellipse and, if so, builds a rectangular drawing that has the same left edge, top edge, width, and height as the ellipse. (If drawing is not an ellipse, rectangularize should just return the drawing.)

For example, the following code should draw a black ellipse on a red rectangle of the same size.

> (define d1 (drawing-ellipse 5 15 20 10))
> (define d2 (recolor-drawing (irgb 255 0 0) (rectangularize d1)))
> (image-show (drawing->image (drawing-group d2 d1) 100 100))

Some of you were unhappy with the scale-drawing procedure, since it not only scaled the drawing, but also scaled the left edge and top edge of the drawing.

Now that we know a bit about the internal representation, it may be easier to resize the drawing without also shifting it.

Write a procedure, (resize-drawing scale drawing) that creates a new drawing by multiplying the width and height by scale, but does not change the left or top edge of the drawing.

You can compare the results of resize-drawing and scale-drawing with the following code.

> (define d1 (drawing-elllipse 5 15 20 10))
> (define d2 (recolor-drawing "red" (scale-drawing 2 d1)))
> (define d3 (recolor-drawing "blue" (resize-drawing 2 d1)))
> (image-show (drawing->image (drawing-group d2 d3) 100 100))

As you might guess, one-two-1 is the list '(1 2). As you might not have guessed, one-two-0 is the value '(1 . 2). That value looks much like a list, but it has a period in the middle. The period is a signal to you that the value is not a list.

Since one-two-0 is not a list, it is not possible to reverse it or to append it to another list.

However, like the typical implementation of cons, the typical implementation of append does not confirm that its second parameter is a list. And, like cons, when given a non-list as a second parameter, append returns a non-list. In this case, append returns '(0 0 1 . 2). Once again, the period indicates “hey, that's not a list”.

Why does Scheme permit these non-lists? Because they are a generalization of lists (or at least of the techniques by which we process lists). As we'll see later in the semester, these non-lists can be quite useful.

Return to exercise 3.