Common Lisp: What is the downside to using this filter function on very large lists?

Question

I want to filter out all elements of list 'a from list 'b and return the filtered 'b. This is my function:

(defun filter (a b)
  "Filters out all items in a from b"
    (if (= 0 (length a)) b
      (filter (remove (first a) a) (remove (first a) b))))

I'm new to lisp and don't know how 'remove does its thing, what kind of time will this filter run in?

Answer 1

There are two ways to find out:

• you could test it with data

• you could analyze your source code

Let's look at the source code.

• lists are built of linked cons cells

• length needs to walk once through a list

• for EVERY recursive call of FILTER you compute the length of a. BAD!

  (Use ENDP instead.)

• REMOVE needs to walk once through a list

• for every recursive call you compute REMOVE twice: BAD!

  (Instead of using REMOVE on a, recurse with the REST.)

• the call to FILTER will not necessarily be an optimized tail call. In some implementations it might, in some you need to tell the compiler that you want to optimize for tail calls, in some implementations no tail call optimization is available. If not, then you get a stack overflow on long enough lists.

  (Use looping constructs like DO, DOLIST, DOTIMES, LOOP, REDUCE, MAPC, MAPL, MAPCAR, MAPLIST, MAPCAN, or MAPCON instead of recursion, when applicable.)

Summary: that's very naive code with poor performance.

Common Lisp provides this built in: SET-DIFFERENCE should do what you want.

http://www.lispworks.com/documentation/HyperSpec/Body/f_set_di.htm#set-difference