CODEWITHSUNDEEP
positionlispsublistremoveall
user1973035
user1973035

Reputation: 33

Lisp - remove from position

I need a function for deleting elements on nth position in starting list and all sublists. I don't need a working code, i just need any advice.

Upvotes: 1

Views: 902

Answers (3)

danlei
danlei

Reputation: 14291

Asking for advice and not the final solution is laudable. I'll try to explain it to you.

Singly linked lists lend themself to being recursively processed from front to end. You have cheap operations to get the first element of a list, its rest, and to build a list by putting a new element at the front. One simple recursion scheme would be: Take the first element from the list, do something with it, then put it at the front of the result of repeating the whole process with the rest of the list. This repetition of the process for successive elements and rests is the recursive part. If you have an empty input list, there is nothing to do, and the empty list is returned, thus ending the processing. This is your base case, anchor, or whatever you want to call it. Remember: Recursive case, base case, check – you need both.

(Because of Lisp's evaluation rules, to actually put your processed element before the processed rest, it must be remembered until the rest is actually processed, since the operation for building lists evaluates both of its arguments before it returns the new list. These intermediate results will be kept on the stack, which might be a problem for big lists. There are methods that avoid this, but we will keep it simple here.)

Now, you're actually asking not only for simple lists, but for trees. Conveniently, that tree is represented as a nested list, so generally the above still applies, except a little complication: You will have to check whether the element you want to process is itself a branch, i.e. a list. If it is, the whole process must be done on that branch, too.

That's basically it. Now, to remove an element from a tree, your operation is just to check if your element matches and, if yes, dropping it. In more detail:

  • To remove an element from an empty list, just return an empty list.

  • If the first element is itself a list, return a list built from the first element with all matches removed as its first, and the rest with all matches removed as its rest.

  • If its first element matches, return the rest of the list with all matching elements removed. (Notice that something gets "dropped" here.)

  • Otherwise, return a list built from the first element as its first and the rest of the list with all maching elements removed as its rest.

Take a look at this and try to find your recursive case, the base case, and what deals with walking the nested tree structure. If you understand all of this, the implementation will be easy. If you never really learned all this, and your head is not spinning by now, consider yourself a natural born Lisp programmer. Otherwise, recursion is just a fundamental concept that maybe hard to grasp the first time, but once it clicked, it's like riding a bicycle.

Ed: Somehow missed the "position" part, and misread – even despite the question title. That's what fatigue can do to people.

Anyway, if you want to delete an element in the tree by position, you can let your function take an optional counter argument (or you can use a wrapping function providing it). If you look at the points above, recursing for a new branch would be the place where you reset your counter. The basic recursion scheme stays the same, but instead of the comparing the element itself, you check your counter – if it matches the position you want to remove, drop the element. In every recursive case, you pass your function the incremented counter, except when entering a new branch, where you reset it, i.e. pass 0 for your counter argument. (You could also just return the rest of the list once the element is dropped, making the function more performant, especially for long lists where an element near the beginning is to be deleted, but let's keep it simple here.)

Upvotes: 3

GoZoner
GoZoner

Reputation: 70205

My approach would be the following:

  1. delete the nth element in the top-level list
  2. recursively delete the nth element in each sublist from the result of #1

I'd implement it this like:

(defun (del n l)
  (defun (del-top-level n l)
    ...) ; return l but with nth gone
  (mapcar #'(lambda (l) (if (not (listp l)) l (del n l)))
          (del-top-level n l)))

You'd need to implement the del-top-level function.

Upvotes: 1

Daniel Williams
Daniel Williams

Reputation: 8885

Ok I think I see what you need.

You should need two functions

The entry function will just call a helper function like (DeleteHelper position position myList)

DeleteHelper will recursively call itself and optionally include the current element of the list if the current position is not 0. Such as (cons (car myList) (DeleteHelper (- position 1) originalPosition (cdr myList))

If DeleteHelper encounters a list, recursively traverse the list with a position reset to the original incoming position. Such as (cons (DeleteHelper originalPosition originalPosition (car myList)) (DeleteHelper (- position 1) originalPosition (cdr myList)))

Also keep in mind the base case (I guess return an empty list once you traverse a whole list).

This should get you in the right direction. It has also been a few years since I wrote any Lisp so my syntax might be a bit off.

Upvotes: -1

Related Questions