CODEWITHSUNDEEP
lispcommon-lisp
Jen
Jen

Reputation: 1

remove with deep recursion in lisp

How can I implement the remove function with deep recursion?

I know how to write remove in shallow recursion, but it's hard to change this into deep recursion.

 (myremove '(1 2) '(1 ((1 2) 3) (4 (5 ((1 2) 5))))) -> (1 (3) (4 (5 (5))))

Upvotes: 0

Views: 1694

Answers (1)

Rörd
Rörd

Reputation: 6681

I suppose by "deep recursion" you're referring to recursion over a tree instead of recursion over a list?

The more low-level answer to this is to recurse down both the car and the cdr of the cons cells, instead of just the cdr. Though I'ld prefer to use higher order functions, in this case calling mapcar recursively:

(defun myremove (item tree)
  (if (atom tree)
      tree
      (mapcar (lambda (subtree) (myremove item subtree))
              (remove item tree :test #'equal))))

EDIT: Here's a low-level solution:

(defun myremove (item tree)
  (cond ((atom tree)
         tree)
        ((equal item (car tree))
         (myremove item (cdr tree)))
        ('otherwise
         (cons (myremove item (car tree))
               (myremove item (cdr tree))))))

Upvotes: 2

Related Questions