Why can't I delete the current element when iterating over a list?

Question

I want to iterate over a list, perform an action with the elements and based on some criteria, I want to get rid of the active element. However, when using the function below I end up in an infinite loop.

 (defun foo (list action test)
   (do ((elt (car list) (car list)))
       ((null list))
     (funcall action elt)
     (when (funcall test elt)
       (delete elt list))))

(setq list '(1 2 3 4))
(foo list #'pprint #'oddp)
-> infinite loop

Is it not possible as it points to itself? In the end, elt is (car list) of course.

Is this a correct assessment? And how could I solve this efficiently?

Answer 1

Actually you can alter the state of your list while iterating over it. You will just have to use rplacd in addition to delete, and control the advancement along the list not in the iteration clause, but inside the do body:

 (defun nfoo (lst action test)
   (do* ((list (cons 1 lst))
         (elt (cadr list) (cadr list)))
        ((null (cdr list))
         (if (funcall test (car lst)) (cdr lst) lst))
     (funcall action elt)
     (if (funcall test elt)
       (rplacd list (delete elt (cddr list)))
       (setf list (cdr list)))))  

You should call it via copy-list if you don't want it to destroy the argument list.

If you want to remove from your list not all elements equal to elt that passed the test, but rather all such that will pass the test, then the delete call will need to be passed the test function as the :test argument.

(edit:) and even much simpler and straightforward, like this (non-destructive) version:

(defun foo (list action test)
   (do* ((elt (car list) (car list)))
        ((null list))
     (funcall action elt)
     (if (funcall test elt)
       (setf list (delete elt list))
       (setf list (cdr list)))))

Answer 2

The loop is infinite since you are not iterating over anything, you apply the action repeatedly, but if it doesn't mutate the element, as pprint obviously doesn't, then if the test result is negative then it will remain so and the list wouldn't empty even if the deletion worked as you attempt it.

DELETE is a destructive function. In Common Lisp destructive operations are allowed to destroy their argument. You are supposed to discard any references to the argument and use only the return value. After the operation is completed there are no guarantees about the state of the argument. In particular, there might be no effect as implementations are also allowed to act identically to a non-destructive counterpart, but usually the component parts of the sequence will be reassembled in some difficult to predict way. You are also destroying a literal in your example, which has undefined behaviour and it should be avoided.

It is generally best to treat lists in Common Lisp as immutable and destructive operations as a microoptization which should only be used when you are sure they won't break anything. For this problem you might want to iterate over the list using LOOP assembling the result list with conditional COLLECT. See the LOOP chapter of PCL.

Answer 3

I'm a bit new to lisp, so perhaps I'm missing something in your question. Still, I think I understand what you're asking, and I wonder why you're not using some existing structures for this... namely remove-if-not (or remove-if if I have things backwards) and mapcar...

(mapcar #'pprint (remove-if-not #'oddp '(1 2 3 4))

The above prints 1 and 3 (and returns (nil nil), but presumably you can ignore that... or you could do a defun that does the above and ends with (values)). (If you wanted the evens, change remove-if-not to remove-if.)

This strikes me as perhaps a more sensible way to go about things, unless you're doing this for pedagogical reasons or I'm missing something... either of which I admit is quite possible. :)

P.S. Hyperspec info on remove-if, remove-if-not, etc.