Lisp in Small Parts

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:

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