Remove all occurences of elem from any level of a list in Common-lisp

Question

I want to solve this problem using mapcar/lambdas. I know how to do it regularly. So far I have something like:

(defun removal (lista elem &optional final)
    (cond
       ((and (atom lista) (eql lista elem))  nil)
       ((listp lista) (mapcan (lambda (e) ( removal e elem final)) lista))
       (t (nconc final lista))))

For some reason, it's not even running so far but this is a draft. Any ideas where to put the mapcar or how to get rid of the optional list final? I need to solve this using either map functions or lambdas and recursion.

Still not working properly even after adding the lambda and mapcan, it won't construct a list at all

Answer 1

You mention using mapcar and lambda, but Common Lisp also includes mapcan which might be more useful here. The mapcan function is like mapcar, but instead of creating a list of the function results, it takes the function results and concatenates them into a list. E.g.,

(mapcan (lambda (x)
          (list x x))
        '(1 2 3))
;=> (1 1 2 2 3 3)

This is handy for filtering type tasks, because you can have the function that you're mapping over the list always return a list, and if it returns nil, then you've essentially filtered out that element. E.g.:

(mapcan (lambda (x)
          (if (evenp x)
              (list x)                  ; if even, return (x)
              '()))                     ; if odd, return ()
        '(1 2 3 4 5 6))
;;=> (2 4 6)

So, you can remove an element from all levels of a tree with something like this. The internal %remove-all function does the actual work, but it always returns a list, even if the original input wasn't a list. So, we just have to extract the first element from it afterward.

(defun remove-all (element tree &key (test #'eql))
  (labels ((%remove-all (element tree)
             (cond
               ((funcall test element tree) '())
               ((atom tree) (list tree))
               (t (list (mapcan (lambda (child)
                                  (%remove-all element child))
                                tree))))))
    (car (%remove-all element tree))))

(remove-all 3 '(1 2 3 (3 2 1 (1 3 2))))
;;=> (1 2 (2 1 (1 2)))

(remove-all 3 5)
;;=> 5

(remove-all 3 3)
;;=> NIL

(remove-all 3 '(3))
;;=> NIL

Answer 2

Since it is not clear what kind of constrains do you have, here there are two solutions, the first one recursive, without higher order functions, and the second one with a higher order function.

(defun remove-from-tree(el tree)
  (cond ((null tree) nil)
        ((consp (car tree))
         (cons (remove-from-tree el (car tree))
               (remove-from-tree el (cdr tree))))
        ((eql (car tree) el) (remove-from-tree el (cdr tree)))
        (t (cons (car tree) (remove-from-tree el (cdr tree))))))

In this solutions there are four possible cases in the cond:

1. if the tree is empty, then return an empty tree,
2. if the first element of the tree is a cons, that is a tree, apply recursively the function to both the car and the cdr of the original tree, and cons the results to obtain the new tree,
3. (at this point we know that the car of the tree is an atom), if the car is eql to the element, then ignore the car and continue to apply recursively the function to the cdr,
4. otherwise, build a new tree with the car (which is an atom that differs from the element) and the result of applying the function to the cdr of the tree.

Here is the second version:

(defun remove-from-tree(el tree)
  (mapcan (lambda(subtree)
            (cond ((null subtree) (list nil))
                  ((consp subtree) (list (remove-from-tree el subtree)))
                  ((eql subtree el) nil)
                  (t (list subtree))))
          tree))

In this case the functional mapcan is used, and since this nconc all the results, we must add list to several branches of the cond of the inner function.

The inner function, which is applied to the “top” elements of the tree, has four cases:

1. if the subtree is null, the value returned is (list nil) so that the mapcan can concatenate this result to the others,
2. if the subtree is a cons, that is a tree, call recursively the function on it and return a list of the result,
3. (at this point we know that the subtree is an atom), if it is equal to the element to be removed, return nil (and this will not appear in the result of the mapcan),
4. finally, returns the atom, different from the element, as a list.

Answer 3

Some remarks:

• when you deal with multiple levels of lists, you are typically working with a tree, aren't you? I would replace removal and lista by tree-remove and tree.

• what if lista is an atom, but not a number? you'd better check if lista is a number before using =, or maybe accept a :test argument.

• You are saying that for some reason, it's not even running. Don't you have an error message? what does it say? something along undefined function: lista? you are using the lista symbol in first position of a list in a normal evaluation context.

• In order to avoid using an optional argument, define a local function with labels. Here is another example to demonstrate how to use labels:

  (defun tree-occurences (tree number)
    (let ((counter 0))
      (labels ((count-occurences (form)
                 (typecase form
                   (sequence (map nil #'count-occurences form))
                   (number (when (= form number) (incf counter))))))
        (count-occurences tree))
        counter))