How to sum a list which contain numbers and letters in Lisp Works

Question

I am trying to define a sum functions which take a list as parameter. The problem is that my list can contains not only numbers, but also letters. So my question is, how can i avoid the letters and continue to verify the rest of the list ?

Exemple : (sum '(a 2 4 b d)) = 6

(defun sum (l) 
    ( if (numberp (CAR l)) (sum (CDR l)) (+ (CAR l) (sum (CDR l))) )
)

All i have is a "Stack overflow" error.

Thanks in advance.

Answer 1

Your code tries to apply a recursive approach. Here it is, properly formatted, with longer names:

(defun sum (list) 
  (if (numberp (car list))
      (sum (cdr list))
      (+ (car list) (sum (cdr list)))))

You have a stack overflow because you did not provide a base case when the list is empty. If you pass a NIL list into your function, what happens?

1. (car list) returns NIL, which is not a number.
2. You go to the else branch.
3. You try to add (car list), which is still NIL, to the recursive call to SUM with (cdr list), which is also NIL.
4. You are back to step one in the recursive call: endless recursion, which eventually triggers an error because you constantly allocate stack frames with each call.

So, you have to define what happens when giving empty lists. This is a typical homework question. My favorite template involves etypecase, because it provides a defensive coding approach that rejects errors early and is quite reader-friendly:

(defun foo (list)
  (etypecase list
    (null <base-case>)
    (cons <general-case>)))

However, you also often find this, or something equivalent with cond:

(defun foo (list)
  (if (null list)
      <base-case>
      <general-case>))

This is probably what is expected from students. A better approach is to use endp instead of null, because the former checks whether the argument is effectively a list.

In your problem:

• The base case obviously returns 0.
• The general case computes the sum of the car (zero if not a number) with the sum of the cdr, obtained recursively.

But then, you will have a recursive function that needs to store intermediate results on the call stack, which is wasteful. In order to have a tail-recursive function, you need to pass the resulting sum as an argument of your function: first you pass 0, then each recursive call first computes the sum before calling itself recursively. The base case returns the sum. That guarantees you that the no intermediate result needs to be stored between recursive invocations, which under the right circumstances (this depends on your implementation) can be optimized away as a loop. But since Common Lisp already provides iteration constructs, you should use them instead in practice:

(loop for e in list when (numberp e) sum e)

If you are interested in higher-order functions, the following works too but allocates an intermediate list (whether this is acceptable or not depends on the expected size of your list):

(reduce #'+ (remove-if-not #'numberp list))