fix the function which removes elments [Common Lisp]

The task is: for given list of elements and X element, remove an element after X if it is not equal to X. Example: (a 8 2 a a 5 a) X=a, expecting (a 2 a a a). I have code that removes an element before X, so it gives me (a 8 a a a) instead. How do I fix it?

(defun purgatory (n w)
  (cond ((null w) nil)
        ((and (eq (cadr w) n) (not (eq (car w) (cadr w)))) (purgatory n (cdr w)))
        ((cons (car w) (purgatory n (cdr w))))))

Solution 1:

You can use the destructuring of for on clauses in loop:

(defun purgatory (list x)
  (cons (first list)
        (loop :for (a b) :on list
              :unless (and (eql a x)
                           (not (eql b x)))
              :collect b)))

Solution 2:

I think you are on the right lines with a recursive algorithm. I think that the algorithm works better as a tail-optimised recursion. You take an in-list and an X, and build up an out-list. The output is reversed, and so reverse needs to be applied at the end, thus:

(defparameter my-list '(a 8 2 a a 5 a))

(defun remove-after (in-list X &optional (out-list '()) (last '()))
  (if (null in-list)
    (reverse out-list)
    (if (and (eql last X) (not (eql (car in-list) X)))
       (remove-after (cdr in-list) X out-list (car in-list)) 
       (remove-after (cdr in-list) X (cons (car in-list) out-list) (car in-list))
    )))

 ; (A 2 A A A)

As for the non-tail algorithm, I think this does it:

(defun purgatory (n w)
  (cond ((null w) nil)
        ((and (eq (car w) n) (not (eq n (cadr w)))) (cons (car w) (purgatory n (cddr w))))
        (t (cons (car w) (purgatory n (cdr w))))
))

; (A 2 A A A)

So, if the first element is n and the next is not n, then add n at the front of the algorithm, but skip cddr the next element. Otherwise, add the first element to the front of the algorithm, no skip cdr.

NB: since you've defined the problem in terms of X, I think this should be one of your parameters, not n