Delete element in list that contains lists

Question

beginner in LISP here. I'm preparing myself for my upcoming exam in LISP and I've come across a problem I can't solve, so I was hoping someone more experienced might help me out.

Anyways, here is my problem : You are given a list that may contain lists as elements. Your task is to delete an atomic element at a given position.

The list and the position are given as input parameters.

Example : Position=5 , List=(1 (2 3) ((4)) (5 (6))) , should return (1 (2 3) ((4)) ((6))).

Here is what i got so far...(PS the code below works thanks to the assistance of imMaw , you can check edit to see my previous mistake ).

(defun number_of_atoms(List)
 (atoms List 0)
)
(defun atoms(List Number)
 (cond
  ((null List) Number)
  ((atom (car List)) (atoms (cdr List) (+ 1 Number)))
  ((+ (atoms (car List) Number) (atoms (cdr List) 0)))
 )
)
(defun deleteElement(Pos List)
 (deleteElementAcc Pos 1 List)
)
(defun deleteElementAcc(Pos CurrPos List)
(cond 
  ((null List) nil)
  ((and (atom (car List)) (not(eql CurrPos Pos))) (cons (car List) (deleteElementAcc Pos (+ CurrPos 1) (cdr List))))
  ((and (atom (car List)) (eql CurrPos Pos)) (deleteElementAcc Pos (+ CurrPos 1) (cdr List)))
  ((cons (deleteElementAcc Pos CurrPos (car List))
         (deleteElementAcc Pos (+ CurrPos (number_of_atoms(car List))) (cdr List))))
)
)

Answer 1

While solving this problem in just any way isn't particularly difficult, it is really non-trivial to solve it well. By well I mean both big O's and code complexity, just as well as handling of corner cases. I'm not sure this code will handle even improper lists, and it has parts that could be certainly reduced in verbosity, but, technically, it is there. It walks through the tree in exactly O(n), where n is the number of elements in the tree, and it uses O(n + 2 * (maximum depth)) space, i.e. it will use the memory already used by the tree and in addition the memory proportional to the maximum depth of the tree.

No attempt was made to identify cyclic lists or duplicates:

(defun remove-from-tree-linear (tree &rest positions)
  (loop with node = tree
     with nilcar = (gensym)
     with positions = (sort (remove-duplicates positions) #'<)
     with counter = 0
     with copy = nil
     with root = nil
     with stack = nil
     with backrefs = nil
     while (or node stack) do
       (cond
         ((null node)
          (setf backrefs (cdr backrefs))
          (when (car stack)
            (setf copy (car backrefs)))
          (setf node (car stack) stack (cdr stack)))
         ((consp (car node))
          (if copy
              (if (eq (car copy) nilcar)
                  (setf (car copy) (list nilcar)
                        copy (car copy)
                        (car backrefs) copy)
                  (setf (cdr copy) (list nilcar)
                        copy (cdr copy)
                        (car backrefs) copy))
              (setf copy (list nilcar)
                    root copy))
          (setf backrefs (cons copy backrefs))
          (setf stack (cons (cdr node) stack)
                node (car node)))
         (t (if (and positions (= counter (car positions)))
                (setf positions (cdr positions))
                (if copy
                    (progn
                      (if (eq (car copy) nilcar)
                          (setf (car copy) (list (car node))
                                copy (car copy))
                          (setf (cdr copy) (list (car node))
                                copy (cdr copy)))
                      (setf (car backrefs) copy))
                    (setf copy (list (car node))
                          root copy
                          backrefs (list copy))))
            (setf node (cdr node))))
       (incf counter)
     finally (return root)))

Answer 2

Why are you spelling Pos and CurrPos with z's in half the places?

And the problem in your code lies in the last branch of the cond. When you recurse on the cdr of List, CurrPos needs to be advanced by the number of elements in (car List). And a simple (length List) won't work, because it needs to recursively count elements in sublists.

Edit: more elaboration Say we call

(deleteElement 3 '((1 2) (3 4)))  

You turn this into

(deleteElementPos 3 1 '((1 2) (3 4))),

which falls into the last case of the cond, and you get

(cons (deleteElementAcc 3 1 '(1 2))
      (deleteElementAcc 3 1 '((3 4))))

notice that currPos is wrong for the cdr of the list - it should be 3, not 1. You actually want your code to turn into

(cons (deleteElementAcc 3 1 '(1 2))
      (deleteElementAcc 3 (+ 1 2) '((3 4))))

because (car List) has 2 elements in it.

So, you just need to change

(deleteElementAcc Pos CurrPos (cdr List))

into

(deleteElementAcc Pos (+ CurrPos (recursive-length (car List))) (cdr List))

and program recursive-length, which is a pretty simple function. It should count elements in sublists, so for example (recursive-length '((1 2) ((3)))) returns 3.