Extracting a list inside a list

Question

I am having problems extracting a list from a list.

(defun delete (a l)
    (cond
       ((null l) nil)
       ((eq (car l) a) (delete a (cdr l)))
       (t (cons (car l) (delete a (cdr l))))))

It deletes whatever is 'a' in a list l but if l consists of another list and a is in that inner list then my program can't reach inside that inner list.

Answer 1

There is not only one possible solution, but I will stay close to your code. Since this is homework, I will not give you a working answer, but I will try to give you some things to think about, and give detailed pointers:

Try to understand what your code does and what you really want it to do:

(defun remove-all (a l)
  (cond ((null l) nil)
        ((eql (car l) a) (delete a (cdr l)))
        (t (cons (car l) (delete a (cdr l))))))

(Renamed to remove-all because delete is already taken, and re-indented in a sane manner.)

For flat lists, the code seems to work; but how about nested lists? Let's look at an easy example:

1. What will happen if you evaluate (remove-all 1 '((1)))?
2. What do you want to happen for that input?
3. How can you achieve it?

Let's take a look:

1. What happens:

   • The list is not null, go on
   • The car is not eq to 1 go on
   • '(1) gets consed to (remove-all '()), yielding '((1))

   So, it failed to recognize that the car is itself a list which should be searched for matching elements. The problem seems to lie between step one and step two.

2. What should be done:

   • Check, if the car is itself a list
   • If yes, invoke remove-all on it
   • Then, cons the result to the cdr, which also needs to be "cleaned" (Hint: But only if there is something to cons)

3. How exactly?

   • Add a cond clause which does the things mentioned under 2 -- Left as homework

Answer 2

You need another clause where you test if the item is a list and when true also recurses into the sublist.