Lists are one of the basic data structures in Lisp. Very often programmers need to manipulate lists. Think of the broad possibility of operations one may want to perform on lists: counting the number of elements in a list; searching for an element in a list; removing a particular element from a list; replacing an element in a list; these represent only a small number of possibilities. All of these problems are inherently recursive. Also, their solutions all follow the same structure.
RULE OF THUMB 1:
When recurring on a list, do three things:
1. check for the termination condition;
2. use the first element of the list;
3. recur with the ``rest'' of the list.
RULE OF THUMB 2:
If a function builds a list using ``cons,'' return () at the
To solve this problem we will have to look at each of the elements of the given list one by one, checking if it is the element to be removed. We know that we can stop searching if we
Write a function, ``remove,'' which takes a list and an element, and
returns the original list with the first occurrence of the element
The following solution clearly shows the three parts of Rule of Thumb 1 and also illustrates the use of Rule of Thumb 2:
The following notation gives an idea of the execution of ``remove'':(defun remove (lst elt) (cond ((null lst) nil) ((equal (first lst) elt) (rest lst)) (t (cons (first lst) (remove (rest lst) elt)))))
Note, Rule of Thumb 1 provides a general framework within which to think about recursion. In different examples, the importance and length of the three components may differ. In the following example the second part of the rule (using the first element of the list) comes into play only implicitly.(remove '(a 1 c 2 c 7) 'c) = (cons 'a (remove '(1 c 2 c 7) 'c)) = (cons 'a (cons '1 (remove '(c 2 c 7) 'c))) = (cons 'a (cons '1 '(2 c 7))) = (cons 'a '(1 2 c 7)) = '(a 1 2 c 7) (remove '(a (1 q) 2) 'q) = (cons 'a (remove '((1 q) 2) 'q)) = (cons 'a (cons '(1 q) (remove '(2) 'q))) = (cons 'a (cons '(1 q) (cons 2 (remove '() 'q)))) = (cons 'a (cons '(1 q) (cons 2 '()))) = (cons 'a (cons '(1 q) '(2))) = (cons 'a '((1 q) 2)) = '(a (1 q) 2)
The solution is:
Write a function, ``length,'' which takes a list and returns a count of
all the top level elements in the list.
We can identify the three components mentioned in Rule of Thumb 1:(defun length (lst) (cond ((null lst) 0) (t (+ 1 (length (rest lst))))))
(first lst), the first element of the list is not forgotten; by adding a one to the result of the recursive call, we keep a track of the top level elements.
(length '(a (2 q) 64)) = (+ 1 (length '((2 q) 64))) = (+ 1 (+ 1 (length '(64)))) = (+ 1 (+ 1 (+ 1 (length '())))) = (+ 1 (+ 1 (+ 1 0))) = (+ 1 (+ 1 1)) = (+ 1 2) = 3
© Colin Allen & Maneesh Dhagat