- Read By
- Friday, Sep 7, 2018
- Summary
- We have our first encounters with Scheme’s list data type. Lists collect values. We explore how to work with lists, including mechanisms for creating lists, applying procedures to all elements in a list, and combining the elements in a list.

In your initial explorations with Scheme you have investigated a variety
of basic types of data, including numbers, strings, and symbols. You can
work on many kinds of problems with just these types. However, when you
want to address more complex problems, particularly problems from data
science, you will need to work with *collections* of data - not just the
rating of a movie from one newspaper, but the rating of that movie from
many newspapers (or even the ratings of many movies from many newspapers).

In Scheme, the simplest mechanism for dealing with lists of data are
*lists*. Lists are collections of values that you can process one-by-one
or *en masse*. Fortunately, there is. In this reading, we will consider
Scheme’s *list* data type as well as a variety of procedures to build
and manipulate lists.

You may recall that there are five basic issues we should consider when
we encounter a new type: its *name*, its *purpose*, how one *expresses*
values in the type, how the computer *displays* values in the type,
and what *operations* are available to you.

We’ve covered the first two: The name of the type is “list” and its purpose is to group or collect values. Let us skip ahead to how lists are displayed. Once you’ve created a list, the Scheme interpreter shows lists in a fairly simple format:

- A single-quotation mark (a.k.a. a tick mark).
- An open parenthesis.
- The elements of the list, separated by spaces.
- A close parenthesis.

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 those 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.
The single-quotation marks also help, but they do not appear in every
implementation of Scheme.

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.

`map`

procedureSo, 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 unary
(one-parameter) 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.

```
> (require csc151/square)
> (require csc151/lists)
> (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)
```

Aren’t approximations wonderful? They get even more interesting when we start rounding.

```
> (map ceiling (map square (map sqrt (list 1 2 3 4 5 6 7 8 9 10))))
'(1 3.0 3.0 4 6.0 6.0 8.0 9.0 9 11.0)
```

What should you take away from this? First, anything you can do to a
single value you can also do to all values in a list by using it with the
`map`

procedure. Second, we often want to do a sequence of operations.

As we just noted, we end up writing `map`

a lot when we want to sequence
operations. Is there a better strategy? Yes. The `csc151/hop`

library
provides a procedure that allows you to *compose* functions. What is
composition? You may remember it from your algebra class. If *f* and
*g* are functions, the composition of *f* and *g*, written *f o g*, is
also a function that applies *g* to its parameter and then *f* to the
*g*’s result..

In traditional notation, we would write

`(f o g)(x) = f(g(x))`

In Scheme notation, we write

`((o f g) x) = (f (g x))`

The cool thing about this compose function is that it can take lots of functions. However, as in the case of the traditional compose, it does them right to left. Hence, the expression we just wrote as

```
> (map ceiling (map square (map sqrt (list 1 2 3 4 5 6 7 8 9 10))))
'(1 3.0 3.0 4 6.0 6.0 8.0 9.0 9 11.0)
```

we can more easily write as

```
> (map (o ceiling square sqrt) (list 1 2 3 4 5 6 7 8 9 10))
'(1 3.0 3.0 4 6.0 6.0 8.0 9.0 9 11.0)
```

And that makes it easier for us to make the results exact, too.

```
> (map (o inexact->exact ceiling square sqrt) (list 1 2 3 4 5 6 7 8 9 10))
'(1 3 3 4 6 6 8 9 9 11)
```

`iota`

You’ve seen three ways to make lists: You can list the individual elements
with `list`

, you can build a list of all the same values with `make-list`

,
and you can create a new list from another list with `map`

.

You may have noted that it’s a bit of a pain to make even a systematic
list like the number from 1 through 10. Hence, we provide some procedures
to make more systematic list. The `(iota n)`

procedure
(from `csc151/lists`

) creates a list of all the non-negative integers
less than `n`

, arranged in increasing order.

```
> (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)
```

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.

When you create a list, you know how many elements are in that list.
After all, you can count. But when you get lists from elsewhere (how?
we’ll see later) or when you’re dealing with longer lists, it is much
easier to have the Scheme interpreter count for you. The `length`

procedure tells you how many elements are in a list.

```
> (length (make-list 5 "hello"))
5
> (length (iota 12))
12
> (length (list 12 1 9 7 2.3 11 5.2 8 9 0 0 0 1 23 1 2))
16
```

When we began our exploration of numbers, we used a variety of unary (one parameter) procedures, such as those above. But we also used some binary (two parameter) operations, such as addition or multiplication. Can we also use those with lists? It seems like we’d want to. For example, if we wanted to compute mean value in a collection of numbers, we want to add up all of the elements in the collection and then divide by the length of the collection.

We’ll start with a simple list of numbers, such as `(list 4 1 6 3 2 10 5)`

.
We’d like to compute `4 + 1 + 6 + 3 + 2 + 10 + 5`

. The `csc151/lists`

library provides a standard procedure, `reduce`

, that does just that.
In particular, `(reduce FUN LST)`

, converts `LST`

to a single value by
repeatedly applying `FUN`

to neighboring pairs of values, replacing the
pair with the result of the function.

```
> (require csc151/lists)
> (define numbers (list 4 1 6 3 2 10 5))
> (reduce + numbers)
31
```

Let’s see …

4+1 is 5. 6+3 is 9. 2+10 is 12. 5+9 is 14. 12+5 is 17. 14+17 is 31.

Yup.

Of course, we could also say

4+1 is 5. 5+6 is 11. 11+3 is 14. 14+2 is 16. 16+10 is 26. And 26+5 is 31.

That’s good. If it doesn’t matter what order we do the addition, we can choose whatever order is most efficient. (If we had lots and lots of numbers to add, it might be good to have different computers to add different subsets of the numbers and then add them back together at the end.) You’ll find that the same holds true for multiplication.

```
> (reduce * numbers)
7200
```

We can, of course, use `reduce`

in many other ways. To find the largest
value in the list, we reduce with `max`

.

```
> (reduce max numbers)
10
```

```
> (reduce min numbers)
1
```

We can also use reduce, like `map`

, with values other than numbers.

```
> (reduce string-append (list "one" "two" "three" "four" "five"))
"onetwothreefourfive"
> (map number->string (iota 5))
'("0" "1" "2" "3" "4")
> (reduce string-append (map number->string (iota 10)))
"0123456789"
> (string->number (reduce string-append (map number->string (iota 10))))
123456789
> (sqrt (string->number (reduce string-append (map number->string (iota 10)))))
11111.111060555555
```

We started this section by asking ourselves about computing the average of a list. We should know have the tools to do so.

Take a moment and think to yourself about how you would compute the
average of the list of values in `numbers`

.

Got it?

We were serious. Think about it.

Okay, here’s what we’d write.

```
> (/ (reduce + numbers) (length numbers))
4 3/7
```

Fairly simple, isn’t it? Computing the geometric mean is only a bit harder. (It’s okay if you don’t know what the geometric mean is; it’s a bit like the mean, except that we multiply the numbers together and then take the root of the product.)

```
> (expt (reduce * numbers) (/ 1 (length numbers)))
3.556702166688497
```

You’ve seen some basic uses of `reduce`

with lists. You will certainly
discover many other applications of reduce.

Here’s a problem. We noted that `reduce`

relies on our ability to
combine neighboring pairs in any order. Are there operations in which
the order in which you combine neighboring pairs matters? Certainly.
Let’s consider subtraction, using the expression (4 - 1 - 6 -
3 - 2 - 10 - 5). Here’s one computation, in which we randomly choose
which pair of numbers to use.

4 - 1 -

6 - 3- 2 - 10 - 5 = 4 - 1 -3- 2 - 10 - 5

4 - 1 -

3 - 2- 10 - 5 = 4 - 1 -1- 10 - 5

4 -

1 - 1- 10 - 5 = 4 -0- 10 - 5

4 - 0- 10 - 5 =4- 10 - 5

4 -

10 - 5= 4 - 5

4 - 5=-1

But that’s probably not what most of us would expect. Let’s see what the procedure does.

```
> (reduce - numbers)
15
> (reduce - numbers)
1
> (reduce - numbers)
25
```

Ooh, that’s not very good, is it. We’d probably like consistent results.

We might, perhaps, take a more systematic approach, either doing the subtraction from left to right or from right to left. We’ll start by working from left to right.

4 - 1- 6 - 3 - 2 - 10 - 5 =*3- 6 - 3 - 2 - 10 - 5

3 - 6- 3 - 2 - 10 - 5 =-3- 3 - 2 - 10 - 5

-3 - 3- 2 - 10 - 5 =-6- 2 - 10 - 5

-6 - 2- 10 - 5 =-8- 10 - 5

-8 - 10- 5 =-18- 5

-18 - 5=-23

But let’s also try working from right to left.

4 - 1 - 6 - 3 - 2 -

10 - 5= 4 - 1 - 6 - 3 - 2 -5

4 - 1 - 6 - 3 -

2 - 5= 4 - 1 - 6 - 3 --3

4 - 1 - 6 -

3 - -3= 4 - 1 - 6 -6

4 - 1 -

6 - 6= 4 - 1 -0

4 -

1 - 0= 4 -1

4 - 1=3

To support these different situations, we also provide `reduce-left`

and
`reduce-right`

.

```
> (reduce-left - numbers)
-23
> (reduce-right - numbers)
3
```

While these two procedures achieve the goal of systematically reducing a list of values by applying a binary procedure, they cannot be easily parallelized because we have chosen a particular sequence of operations.

`map`

with multiple listsWe’ve seen one way to use binary procedures with lists: We can reduce
a list of values to a single value by repeatedly combining pairs of
values with a function. But there’s another. Just as we can use `map`

to create a new list of values by applying a unary procedure to each
element of a list, we can also use a more generalized version of `map`

that grabs values from multiple lists and combines them into values
in a new list. In particular, `map`

can also build 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) ; That's 1*4, 2*5, and 3*6
> (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")
```

You may be starting to see some interesting possibilities. If you are not, stay tuned.

Scheme comes with a useful procedure, `sort`

, that puts the elements
of a list in an order you specify. The difficulty, of course, is how
to specify the order. For now, we’ll use four basic orderings.

`(sort nums <)`

sorts a list of real numbers from smallest to largest.`(sort nums >)`

sorts a list of real numbers from largest to smallest.`(sort strings string-ci<?)`

sorts a list of strings from alphabetically first to alphabetically last.`(sort strings string-ci>?)`

sorts a list of strings from alphabetically last to alphabetically first.

For example,

```
> (sort (list 5 1 4 2 3) <)
'(1 2 3 4 5)
> (sort (list 5 1 4 2 3) >)
'(5 4 3 2 1)
> (sort (list "Computers" "are" "sentient" "and" "malicious") string-ci<?)
'("and" "are" "Computers" "malicious" "sentient")
> (sort (list "Computers" "are" "sentient" "and" "malicious") string-ci>?)
'("sentient" "malicious" "Computers" "are" "and")
```

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)`

procedure 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 `(take lst n)`

procedure builds a new list
consisting of the first * n* elements of

`lst`

```
> (take (reverse (iota 10)) 7)
'(9 8 7 6 5 4 3)
```

The `(drop lst n)`

procedure builds a new list consisting of all but the first * n* elements of

`lst`

```
> (drop (iota 10) 3)
'(3 4 5 6 7 8 9)
```

The `(index-of val lst)`

procedure tells you the position (index)
of a value in the list. In Scheme, the position of a value is the
number of items you must drop from the list to get to the value.
If the value is not in the list, `index-of`

returns -1.

```
> (define observation (list "Computers" "are" "sentient" "and" "malicious"))
> observation
'("Computers" "are" "sentient" "and" "malicious")
> (index-of "sentient" observation)
2
> (drop observation 2)
'("sentient" "and" "malicious")
> (index-of "wicked neat" observation)
-1
```

The `(list-ref lst index)`

procedure is almost the inverse of `index-of`

.
Given a list and a position, `list-ref`

returns the value at that position.

Predict the results of evaluating each of the following expressions.

```
(list 2 1)
(make-list 1 2)
(make-list -1 2)
(map - (iota 2))
(map - (iota 2) (list 2 1))
(map iota (list 2 1))
```

You may verify your predictions with DrRacket.

We came up with three different results for the expression (4 - 1 - 6 - 3 - 2 - 10 - 5). Come up with one or two more and show their derivation.