## Processing Items in a List

In this lesson we are going to show how to perform the same set of operation on every item in a list.

### Finding the sum of a list of numbers

Let's look at the problem of writing a program **sum-list** to find the sum of a list of numbers. We would want to be able to call it like this:

CL-USER > (sum-list '(2 3 5 7 11 13 17 19)) 77

The trick of solving a problem in Lisp is to break it down into simpler problems. We could write the solution in English as follows:

To find the sum of a list of numbers:

- If the list is empty the answer is 0
- Otherwise the answer is the first number added to the sum-list of the remaining numbers.

At first sight we haven't solved the problem, because we still have to find "the sum of the remaining numbers". But this is a shorter list than the one we started with, and after many applications of the procedure this will be an empty list, which we know how to solve.

The way we write this in Lisp is very like the description in English:

(defun sum-list (numbers) (if (null numbers) 0 (+ (first numbers) (sum-list (rest numbers)))))

We have written a program that will find the sum of an unlimited number of numbers. We can give it a list of a million numbers and it will work as expected!

### Recursion

The procedure **sum-list** repeats an operation over a list of items by including a call to itself within its definition. This is called **recursion**. It doesn't result in an infinite loop, as you might at first expect, because of the test **(if (null numbers) ...** which ends the recursion.

In most other computer languages the natural way to implement **sum-list** would be using an iteration construct, such as **for ... next** or **do ... until**. In Lisp, recursion often provides a neater and more intuitive way of solving problems like this.

### Doubling every number in a list

What about the problem of creating a new list which is identical to the original list, but with every number doubled? We would want this to work as follows:

CL-USER > (double-list '(2 3 5 7 11 13 17 19)) (4 6 10 14 22 26 34 38)

The solution in English as follows:

To double a list of numbers:

- If the list is empty the answer is nil
- Otherwise the answer is the list constructed from twice the first number, followed by double the list of the remaining numbers.

The procedure in Lisp is as follows:

(defun double-list (numbers) (if (null numbers) nil (cons (* 2 (first numbers)) (double-list (rest numbers)))))

It's very similar to the definition of **sum-list**, except that we use **cons** to construct a new list and return that as the answer.

### The procedures **sum-list** and **double-list** are useful prototypes for solving a whole range of problems involving working with lists.

**sum-list**operates on every element of a list and returns a single result.**double-list**operates on every element of a list and returns a new, transformed, list.

In a later lesson we'll see how to generalise these two procedures into generic tools that we can use for a wide range of applications.

### Doing something for each element in a list: dolist

Finally I should mention a built-in Lisp construct, **dolist**, that often provides a convenient way of performing a series of operations on every element in a list.

It is written like this:

```
(dolist (item list)
body)
```

where:

**list**is a list of elements.**item**is set to each element of the list in turn.**body**is one or more Lisp procedures that are executed for each value of**item**.

For example:

(dolist (i '(2 3 5 7 11)) (print (* i 2)))

will print:

4 6 10 14 22

### Exercises

In the following exercises, adapt either **sum-list** or** double-list** as appropriate to solve the problem:

#### 1. Count the number of elements in a list

Write a procedure **count-list** to count the number of elements in a list. So:

`(count-list '(2 3 5 7 11 13 17 19)`

should return 8.

#### 2. Reverse each string in a list of strings

Write a procedure **reverse-list** to reverse each word in a list of words. For example:

(reverse-list '("dog" "pan" "tar" "tip" "net"))

should return:

("god" "nap" "rat" "pit" "ten")

#### 3. Find whether each number in a list is even or odd

Write a procedure **evenp-list** to process a list of numbers, replacing each number by **t** if it's even, and **nil** if it's odd. So:

(evenp-list '(1 2 3 4 5 6 7 8))

should return:

(nil t nil t nil t nil t)

#### 4. Find the maximum element of a list

Write a procedure **max-list** to return the maximum element of a list. So:

(max-list '(11 13 17 19 2 3 5 7))

should return 19.

#### 5. Duplicate each element in a list

Write a procedure **dupli-list** to duplicate the elements of a list. For example:

(dupli '(a b c c d))

should give:

(A A B B C C C C D D)

#### 6. Eliminate consecutive duplicates in a list

Write a procedure **compress** that replaces repeated elements with a single copy of the element. The order of the elements should not be changed.

(compress '(a a a a b c c a a d e e e e))

should give:

(A B C A D E)

#### 7. interleave two lists

Write a procedure interleave that will interleave two lists. You can assume they are the same length. For example:

(interleave '(a b c) '(d e f))

should give;

(A D B E C F)

#### 8. Look up an entry in an association list

An association list is a way of storing data as a list of entries. Each entry is a list in which the first item is a unique key; for example:

(defparameter *type* '((cat mammal) (dog mammal) (lizard reptile) (salmon fish)))

Write a procedure **lookup** that takes a key and an association list, and returns the entry that matches the key. For example:

(lookup 'cat *type*)

should give:

(cat mammal)

If the key is not found **lookup** should return nil.

blog comments powered by Disqus