This reading is not yet ready for public consumption. Summary: In our exploration of iteration (a form of repetition), we learned of the values of lists, collections of values that we can iterate over. In this reading, we explore lists in more detail, including how to build lists and how to extract values from lists.

Motivating problem: Want to iterate, but need a group of values for each step of the iteration (e.g., an angle and distance to move a turtle; a color and brush to draw). Consider a problem in which we want to define a series of simple strokes that a turtle will make. A stroke consists of a color, brush, distance, and angle to turn when finished. We then write something like the following to make a turtle make a stroke. (define turtle-stroke! (lambda (turtle stroke) (turtle-set-color! turtle (get-color stroke) (turtle-set-brush! turtle (get-brush stroke) (turtle-forward! turtle (get-distance stroke)) (turtle-turn! turtle (get-angle stroke)))) (define stroke-a (make-stroke "red" "Circle (01)" 10 5)) (define stroke-b (make-stroke "green" "Circle (03)" 15 10)) (define stroke-c (make-stroke "blue" "Circle (01)" 10 -5)) After defining a few simple strokes, we could then draw them with > (foreach (l-s turtle-action! tommy) (list stroke-a stroke-a stroke-b stroke-c stroke-c stroke-b stroke-b stroke-b stroke-b)) But how do we represent a stroke? Fortunately, Scheme, like Lisp before it, provides a simple and elegant mechanism for represent collections of data, the list. In contrast to Scheme's unstructured data types, such as symbols and numbers, lists are structures that contain other values as elements. In particular, a list is an ordered collection of values. We have traditionally used lists of homogenous values as things to iterate over. In Scheme, lists can also be heterogeneous, in that they may contain different kinds of values. For example, we can use a list to gather a color name, brush name, distrance, and angle. (define stroke-a (list "red" "Circle (01)" 10 5)) (define stroke-b (list "green" "Circle (03)" 15 10)) (define stroke-c (list "blue" "Circle (01)" 10 -5)) So far, we only know how to iterate over a list to do something with each value or to transform each value. But the heterogeneous lists we are using for strokes suggest that we will need to figure out other things to do with lists. How do we extract the color, brush, distance, and angle from each stroke? How do we easily make a modified version of one of these strokes, e.g., by replacing the brush or color? Those problems, and a variety of related ones, are the subjects of this reading.

How does Scheme show you that something is a list? It surrounds the list with parentheses and separates the items with spaces. > (list 5 7 11) (5 7 11) > (iota 6) (0 1 2 3 4 5) > (list "red" "Circle (01)" 4 5) ("red" "Circle (01)" 4 5) > (list 'f "red" "blue") (f "red" "blue") You may note something potentially ambiguous about these displayed lists. ...

Given a list, we extract the element n with (list-ref lst n). The first element is element 0. (Values in lists are indexed by the number of values that precede them.) For example, in the list ("red" "green" "blue"), element 0 is "red", element 1 is "green", and element 2 is "blue". Experienced Scheme programmers know that there are some more concise (and, usually, more efficient) ways to extract some parts of a list. You can get the first element (that is, element 0) with car. You can get a list that has its first element deleted with cdr. You can get the second element of a list with cadr. And yes, it's clear that these names are a way of forming an in group. Show how to use these ideas to build strokes, and then show a variety of simple drawings.

Introduce cons and nil.

You may recall that, at the beginning of this reading, we asked how we might take one color of stroke and make a similar stroke that is a different color. We can't change the original stroke: Lists, like drawings, are immutable. Hence, the best we can do is to build a modified version of the list using the basic list operation. For example, we can build a blue stroke similar to stroke-a with the following. > (define stroke-d (cons "blue" (cdr stroke-a)) Note that we used cdr to get the list without the color, and then used cons to put the new color on the front of the list. It is a bit harder to build a variant of stroke-a in which we change the brush. In this case, we get the last two elements of the list (distance and angle) but calling cdr twice. But we're now putting two things on the front, so there will be two calls to cons. > (define stroke-e (cons (car stroke-a) "Circle (05)" (cdr (cdr stroke-a))))

Scheme provides two basic predicates for checking whether a value is a list. The null? predicate checks whether a value is the empty list. The list? predicate checks whether a value is a list (empty or nonempty). > (null? null) #t > (list? null) #t > (null? (list 1 2 3)) #f > (list? (list 1 2 3)) #t > (null? 5) #f > (list? 5) #f

It turns out that you can build any other list procedure with just null, cons, car, cdr, null?, and some other programming techniques. Nonetheless, there are enough common operations that most programmers want to do with lists that Scheme includes them as basic operations. (That means you don't have to define them yourself.) Here are four that programmers frequently use.

The length procedure takes one argument, which must be a list, and computes the number of elements in the list. (An element that happens to be itself a list nevertheless contributes 1 to the total that length computes, regardless of how many elements it happens to contain.) > (length null) 0 > (length (list 1 2 3)) 3 > (length (list (list 1 2 3))) 1

The reverse procedure takes a list and returns a new list containing the same elements, but in the opposite order. > (reverse (list "white" "grey" "black")) ("black" "grey" "white")

We needed strokes. We decided to use lists to represent strokes. That means we know how to extract the various parts, and even to build strokes. However, it is much better to add a layer of abstraction, and hide the underlying implementation from the client programmer. That way, if we decide to change the representation, all we need to do is to change our own procedures. Not this ... But this ...