CODEWITHSUNDEEP
listcommon-lisp
Dick Tucker
Dick Tucker

Reputation: 45

Recursively remove n-th element of all sub-lists (with restrictions) in Common Lisp

I'm a couple of weeks in my study of Lisp (mostly recursion). So far, I've mostly been dealing with simple enough functions that test the basic knowledge of recursion (car, cdr, cond, remove, nth etc.). I stumbled upon a simple problem that I just can't get right. The problem goes:

Write a function remove-nth that takes two arguments:

(defun remove-nth (n l)

)

Where n is a non-negative integer and list is a list/atom/null. The function removes the n-th element (one-based indexing) of the original list and any-level sub-lists that it contains. The operation can be either destructive or non-destructive.

So, for example:

(remove-nth 3 '((1 2 3 4) ((1 3 5) 3 1) (1 2 2 1))) --> ((1 2 4) ((1 3) 3))

What I've tried:

(defun remove-nth (n L)
   (cond
       ((null L) nil)
       ((listp L)
            (cons (remove-nth n (car (r n L))) (remove-nth n (cdr (r n L)))))
       (t L)      
   )
)

(defun r (n L)   
    (remove (nth (- n 1) L) L)
)

This code doesn't work because it sometimes removes an element twice from the same list, e.g. calling:

(remove-nth 2 '((1 2 3 4) ((1 3 5) 3 1) (1 2 2 1)))

ought to output

((1 3 4) (1 2 1))

but in my case, it outputs:

((1 3) (1 1))

i.e. the sub-list (1 2 2 1) has two elements removed instead of just one. I reckon there is an oversight in the way I'm trying to handle the recursive calls, but I've tried many different approaches and I can't get any to work. So, I've turned to you guys for help.

I am not asking for the code per se, but rather an explanation, or a hint on how to better my approach.

Thanks in advance!

Upvotes: 0

Views: 1134

Answers (1)

Paweł Motyl
Paweł Motyl

Reputation: 1342

Look at this code, it should work as you wanted:

(defun remove-nth (n L)
   (cond
       ((null L) nil)
       ((listp L)
        (map 'list (lambda (l) (remove-nth n l)) (r n L)))
       (t L)))

(defun r (n L)                                     
   (if (or (= n 1) (null L)) 
      (cdr L) 
      (cons (car L) (r (1- n) (cdr L)))))

There are 2 problems with your approach:

  1. In function r you're not removing the nth element - you're removing every element that's equal to the nth element of the list. Because of that the list '(1 2 2 1) is transformed to '(1 1) - the 2nd element is 2, so every 2 is removed.
  2. In function remove-nth you're recursing down into the first element and right into the tail of the list - because of the second recursion you're removing more elements that you should. That's apparent in the case of the list '(1 2 3 4). It becomes '(1 3 4) after the call to r, then you decompose it into car (equal to 1) and cdr (equal to '(3 4)). After recursing into the second one, you once again remove the 2nd element and you get '(3). This, after cons, gives you the list '(1 3).

Upvotes: 1

Related Questions