Common Lisp: How to return a list without the nth element of a given list?

Asked 25/2, 2012 at 14:33 Answered 15/5, 2021 at 15:51

I've a question, how to return a list without the nth element of a given list? E.g., given list: (1 2 3 2 4 6), and given n = 4, in this case the return list should be (1 2 3 4 6).

Footworn answered 25/2, 2012 at 14:33 Comment(3)

If this is homework, please add the "homework" tag. – Damned 25/2, 2012 at 14:36

@dasblinkenlight Lisp homework? I think not – Howlett 25/2, 2012 at 21:10

@SethCarnegie, it's rare, but it happens. – Mchail 26/2, 2012 at 2:59

A simple recursive solution:

(defun remove-nth (n list)
  (declare
    (type (integer 0) n)
    (type list list))
  (if (or (zerop n) (null list))
    (cdr list)
    (cons (car list) (remove-nth (1- n) (cdr list)))))

This will share the common tail, except in the case where the list has n or more elements, in which case it returns a new list with the same elements as the provided one.

Mchail answered 25/2, 2012 at 17:49 Comment(14)

+1: I wrote procedural DO based version manually building the result and it was (on SBCL) 4 times faster and half consing compared to the remove-if approach, but this is much cleaner and with the same performance... – Tulle 25/2, 2012 at 20:58

@6502: If you're concerned about performance, did you try using delete-if instead of remove-if? On CCL, this destructive version is an order of magnitude faster and less consing with the default optimize settings and without further tweaks. (Tested with a list of 100k elements, dropping an element in the middle.) – Downpipe 25/2, 2012 at 22:1

@danlei: that means changing the original problem. This versions is non-destructive and shares the tail. To make a non-destructive version out of a destructive one you need to make a full copy first and then my guess is that the end result of copy / destructive version will cons more and will be slower. – Tulle 25/2, 2012 at 23:16

@6502, the original question doesn't say if modifying the input list is forbidden or if the output list should share structure. I generally prefer my functions to be nondestructive and share structure, but I don't see anything in the question prohibiting modifying the input. C and Java programmers would likely find that to be a natural thing to do. And in some situations, the shared tail might be a liability instead of an asset. – Mchail 26/2, 2012 at 3:5

@danlei, if your list has 100k elements, it might be time to consider a more complex data structure ;) – Mchail 26/2, 2012 at 3:12

@Tulle Yes, it's a change in semantics compared to the provided solutions, but I agree with @Samuel in that it's perfectly compatible with the given specification. You're right, making this destructive version non-destructive using copy-list would neutralize the performance/consing advantage. However, if one knows what they're doing, resorting to destructive operations is a legitimate means to improve performance. I just wanted to point out another possibility that improves perfomance of my original solution by an order of magnitude by just changing a single word. – Downpipe 26/2, 2012 at 5:12

@SamuelEdwinWard Well, measuring with a smaller list inside a loop maybe would've been more realistic, but I was lazy. :) – Downpipe 26/2, 2012 at 5:17

By the way: While I prefer having non-destructive functions by default, destructive versions are, in a way, the more general solution. You could turn any destructive operation into a non-destructive one by copying its argument – Making a non-destructive function destructive, however, usually takes a rewrite. (This is just meant to be a side note, not an argument for having destructive operations as an default in general.) – Downpipe 26/2, 2012 at 5:34

I agree that "internally destructive, externally pure" approach of writing functions (like my do/(setf (cdr x) y)) doesn't scale by composition. I'm no Common Lisp expert, but as the problem is stated however ("return a list without the nth element of a given list") I'd assume that a destructive operation would be surprising... but may be it's me (and I've been for example bitten in the past by sort being destructive and not being named nsort). – Tulle 26/2, 2012 at 7:17

actually, I don't think this is right. The OP clearly indicates 1-based indexing; and if n > length(lst), then what happens?? (the last sentence is wrong too). – Molasses 26/2, 2012 at 17:51

@WillNess, in what way does the question indicate 1-based indexing? When index 4 is removed, the fifth element disappears. You're right about n > length though, I'm not sure how I missed that. – Mchail 27/2, 2012 at 1:45

@SamuelEdwinWard quote: " E.g., given list: (1 2 3 2 4 6), and given n = 4, in this case the return list should be (1 2 3 4 6)." With 0-based indexing, the result would have to be (1 2 3 2 6) which is what your code produces, too. The last sentence should speak of "less than n elements". Small stuff, off-by-1 &the like. :) – Molasses 27/2, 2012 at 8:32

also, what if the list is circular and n is negative? (and for destructive versions, what if n is greater than the circular list's period?) – Molasses 27/2, 2012 at 10:31

@WillNess, you're right about the 1-based indexing in the question too; some part of my brain refused to read it correctly. – Mchail 8/5, 2012 at 19:19

Using remove-if:

(defun foo (n list)
  (remove-if (constantly t) list :start (1- n) :count 1))

butlast/nthcdr solution (corrected):

(defun foo (n list)
  (append (butlast list (1+ (- (length list) n))) (nthcdr n list)))

Or, maybe more readable:

(defun foo (n list)
  (append (subseq list 0 (1- n)) (nthcdr n list)))

Using loop:

(defun foo (n list)
  (loop for elt in list
        for i from 1
        unless (= i n) collect elt))

Downpipe answered 25/2, 2012 at 16:16 Comment(11)

Btw: Interesting, how I got two upvotes for a wrong solution. Having worked almost exclusively with Haskell for a few months, I initially used butlast like take in the butlast/nthcdr solution. (Thinking along the lines of take n xs ++ drop (n+1) xs) – Downpipe 25/2, 2012 at 18:0

I upvoted you for the reason that I've been writing in Haskell lately, and mentally did the same thing...oops – Maxinemaxiskirt 25/2, 2012 at 18:18

@Maxinemaxiskirt Great minds err alike? ;) Anyway, it's corrected now – no harm done. – Downpipe 25/2, 2012 at 18:43

or with nconc: (defun nfoo (n ls) (nconc (butlast ...) ...)). But the check for n > (length ls) case is missing. Only the loop version is working then. – Molasses 26/2, 2012 at 18:2

@WillNess Yes, if this was to be used in a library, or in situations where proper inputs are not guaranteed, one should maybe add an (assert (<= 1 n (length list))), or make the implementations just return the original list. (BTW, on CCL the remove-if and loop versions both do the latter.) – Downpipe 26/2, 2012 at 20:34

what's a CCL? (forgive the ignorance) :) I tested in CLisp; only loop worked properly. – Molasses 26/2, 2012 at 20:48

@WillNess A Common Lisp implementation: clozure.com/clozurecl.html (The successor of Coral Common Lisp, the later Macintosh Common Lisp.) – Downpipe 26/2, 2012 at 20:52

thanks! thought of something just now - for circular lists your loop version won't terminate. I guess it means that only the simple recursive copying-sharing version of Samuel E. W. will be the right answer, after the one-off error is corrected there. – Molasses 27/2, 2012 at 10:40

@WillNess Yes, to make this work with circular lists (in an eager laguage like CL), Samuel's solution would probably be the most straightforward approach. I disagree about my solutions being incorrect, though – By that reasoning remove-if itself would have to be considered incorrect, since it doesn't terminate despite its given :start and :count (woudn't work with :end either) parameters. Rather, I would think of circular lists as a special case. (In fact, per the standard, circular lists aren't proper lists at all.) – Downpipe 27/2, 2012 at 18:7

The last 2 (append and loop) are most readable and intuitive. An overdose in Haskell produces weird stuff like the other ones :) – Shafting 14/6, 2023 at 23:19

@Shafting Hehehe, thanks, I'm recovering. :) – Downpipe 22/6, 2023 at 12:13

Here's an interesting approach. It replaces the nth element of a list with a new symbol and then removes that symbol from the list. I haven't considered how (in)efficient it is though!

(defun remove-nth (n list)
    (remove (setf (nth n list) (gensym)) list))

Blythe answered 14/3, 2012 at 19:25 Comment(1)

(defun delete-nth (n list) (delete (setf (nth n list) (gensym)) list)) – Gastight 23/12, 2015 at 19:42

(loop :for i :in '(1 2 3 2 4 6) ; the list
              :for idx :from 0
              :unless (= 3 idx) :collect i) ; except idx=3
;; => (1 2 3 4 6)

loop macro can be very useful and effective in terms of generated code by lisp compiler and macro expander.

Test run and apply macroexpand above code snippet.

Equalize answered 9/12, 2019 at 11:38 Comment(2)

Please explain that how your answer will help to solve the problem, and just dont give code only answer without context – Pertinent 9/12, 2019 at 17:4

Sorry, I thought the context is already given by the question. – Equalize 11/12, 2019 at 1:11

A slightly more general function:

(defun remove-by-position (pred lst)
  (labels ((walk-list (pred lst idx)
             (if (null lst)
                 lst
                 (if (funcall pred idx)
                     (walk-list pred (cdr lst) (1+ idx))
                     (cons (car lst) (walk-list pred (cdr lst) (1+ idx)))))))
    (walk-list pred lst 1)))

Which we use to implement desired remove-nth:

(defun remove-nth (n list)
  (remove-by-position (lambda (i) (= i n)) list))

And the invocation:

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

Edit: Applied remarks from Samuel's comment.

Indefectible answered 25/2, 2012 at 15:37 Comment(1)

Interesting, and something I think I've wanted before. I'd suggest renaming your remove-nth to... something else... remove-by-position? And defining remove-nth (defun remove-nth (n list) (remove-by-position (lambda (i) (= i n)) list). – Mchail 26/2, 2012 at 3:10

A destructive version, the original list will be modified (except when n < 1),

(defun remove-nth (n lst)
  (if (< n 1) (cdr lst)
    (let* ((p (nthcdr (1- n) lst))
           (right (cddr p)))
      (when (consp p)
        (setcdr p nil))
      (nconc lst right))))

That's elisp but I think those are standard lispy functions.

Raised answered 19/6, 2016 at 22:55 Comment(0)

For all you haskellers out there, there is no need to twist your brains :)

(defun take (n l)
  (subseq l 0 (min n (length l))))
(defun drop (n l)
  (subseq l n))
(defun remove-nth (n l)
  (append (take (- n 1) l)
      (drop n l)))

Shafting answered 15/5, 2021 at 15:51 Comment(0)

My horrible elisp solution:

(defun without-nth (list n)
  (defun accum-if (list accum n)
    (if (not list)
        accum
          (accum-if (cdr list) (if (eq n 0) accum (cons (car list) accum)) 
            (- n 1))))
  (reverse (accum-if list '() n)))

(without-nth '(1 2 3) 1)

Should be easily portable to Common Lisp.

Antithesis answered 25/2, 2012 at 15:23 Comment(1)

In Common Lisp local functions are introduced with FLET and LABELS. – Actomyosin 25/2, 2012 at 19:41

A much simpler solution will be as follows.

(defun remove-nth (n lst)
    (append (subseq lst 0 (- n 1)) (subseq lst n (length lst)))
)

Merino answered 26/10, 2012 at 1:30 Comment(0)

Hot tags

Godot Unity Godot Help Programming Godot 4.X GUI GDScript 3D 2D Physics CSharp Godot 3.X VR XR Projects C++

Recommended topics

Hot tags