Is there a common lisp macro for popping the nth element from a list?

Question

I'm pretty fresh to the Common Lisp scene and I can't seem to find an quick way to get the nth element from a list and remove it from said list at the same time. I've done it, but it ain't pretty, what I'd really like is something like "pop" but took a second parameter:

(setf x '(a b c d))
(setf y (popnth 2 x))
; x is '(a b d)
; y is 'c

I'm pretty sure that "popnth" would have to be a macro, in case the parameter was 0 and it had to behave like "pop".

EDIT: Here's my crap first version:

(defmacro popnth (n lst)
  (let ((tempvar (gensym)))
    `(if (eql ,n 0)
      (pop ,lst)
      (let ((,tempvar (nth ,n ,lst)))
        (setf (cdr (nthcdr ,(- n 1) ,lst)) (nthcdr ,(+ n 1) ,lst))
        ,tempvar))))

Trembles

Why do you call it pop? It would be more clear to call it remove-at. Also, there is no need for macro here. – Shaner

@Shaner : POP is the name chosen by the creators of Common Lisp, not me. – Trembles

But it's called pop because you can use the list as a stack data structure (en.wikipedia.org/wiki/Stack_%28data_structure%29). You push stuff to a stack and then pop it from the top. You can't pop it from the middle, so actually leppie is right :) – Mauser

I'm not the first to give pop an optional position, Python does that, too. – Trembles

Answer 1

I came up with a solution that is a little more efficient than my first attempt:

(defmacro popnth (n lst)
  (let ((t1 (gensym))(t2 (gensym)))
    `(if (eql ,n 0)
      (pop ,lst)
      (let* ((,t1 (nthcdr (- ,n 1) ,lst))
              (,t2 (car (cdr ,t1))))
        (setf (cdr ,t1) (cddr ,t1))
        ,t2))))

Here is it in action:

[2]> (defparameter *list* '(a b c d e f g))
*LIST*
[3]> (popnth 3 *list*)
D
[4]> *list*
(A B C E F G)
[5]> (popnth 0 *list*)
A
[6]> *list*
(B C E F G)

Trembles

Answer 2

Something like this:

Removing the nth element of a list:

(defun remove-nth (list n)
  (remove-if (constantly t) list :start n :end (1+ n)))

constantly returns a function, that always returns its argument.

As a macro that accepts a place, using define-modify-macro:

(define-modify-macro remove-nth-f (n) remove-nth "Remove the nth element")

POP-NTH

(defmacro pop-nth (list n)
  (let ((n-var (gensym)))
    `(let ((,n-var ,n))
       (prog1 (nth ,n-var ,list)
         (remove-nth-f ,list ,n-var)))))

Example:

CL-USER 26 > (defparameter *list* (list 1 2 3 4))
*LIST*

CL-USER 27 > (pop-nth *list* 0)
1

CL-USER 28 > *list*
(2 3 4)

CL-USER 29 > (pop-nth *list* 2)
4

CL-USER 30 > *list*
(2 3)

Ingenuity

I'm no lisp guru, but isn't the macro wrong because 1) evaluates n first, 2) evaluates list twice (once for nth and once for the updating macro) ? – Fluctuant

Answer 3

Yes, Lisp has a macro for popping the N-th element of a list: it is called pop.

$ clisp -q
[1]> (defvar list (list 0 1 2 3 4 5))
LIST
[2]> (pop (cdddr list))
3
[3]> list
(0 1 2 4 5)
[4]> 

pop works with any form that denotes a place.

The problem is that, unlike cddr, nthcdr isn't an accessor; a form like (nthcdr 3 list) does not denote a place; it works only as a function call.

Writing a specialized form of pop is not the best answer; rather, we can achieve a more general fix by writing a clone of nthcdr which behaves like a place accessor. Then the pop macro will work, and so will every other macro that works with places like setf and rotatef.

;; our clone of nthcdr called cdnth
(defun cdnth (idx list)
  (nthcdr idx list))

;; support for (cdnth <idx> <list>) as an assignable place
(define-setf-expander cdnth (idx list &environment env)
   (multiple-value-bind (dummies vals newval setter getter)
                        (get-setf-expansion list env)
     (let ((store (gensym))
           (idx-temp (gensym)))
       (values dummies
               vals
               `(,store)
               `(let ((,idx-temp ,idx))
                  (progn
                    (if (zerop ,idx-temp)
                      (progn (setf ,getter ,store))
                      (progn (rplacd (nthcdr (1- ,idx-temp) ,getter) ,store)))
                    ,store))
               `(nthcdr ,idx ,getter)))))

Test:

$ clisp -q -i cdnth.lisp 
;; Loading file cdnth.lisp ...
;; Loaded file cdnth.lisp
[1]> (defvar list (list 0 1 2 3 4 5))
LIST
[2]> (pop (cdnth 2 list))
2
[3]> list
(0 1 3 4 5)
[4]> (pop (cdnth 0 list))
0
[5]> list
(1 3 4 5)
[6]> (pop (cdnth 3 list))
5
[7]> list
(1 3 4)
[8]> (pop (cdnth 1 list))
3
[9]> list
(1 4)
[10]> (pop (cdnth 1 list))
4
[11]> list
(1)
[12]> (pop (cdnth 0 list))
1
[13]> list
NIL
[14]> 

A possible improvement to the implementation is to analyze the idx form and optimize away the generated code that implements the run-time check on the value of idx. That is to say, if idx is a constant expression, there is no need to emit the code which tests whether idx is zero. The appropriate code variant can just be emitted. Not only that, but for small values of idx, the code can emit special variants based on the "cadavers": cddr, cdddr, rather than the general nthcdr. However, some of these optimizations might be done by the Lisp compiler and thus redundant.

Leicestershire

Answer 4

I have same suspicion as @6502...If I remember right...Neither push nor pop can be defined as modify-macros, the former because the place is not its first argument, and the latter because its return value is not the modified object.

Definition of define-modify-macro

An expression of the form (define-modify-macro m (p1 ... pn) f) defines a new macro m, such that a call of the form (m place a1 ... an) will cause place to be set to (f val a1 ... an), where val represents the value of place. The parameters may also include rest and optional parameters. The string, if present, becomes the documentation of the new macro.

I have this popnth works just fine:

(defun nthpop (index lst)
  (pop (nthcdr (1- index) lst)))

> *list*
(1 2 3 4 5)
> (nthpop 2 *list*)
2
> *list*
(1 3 4 5)

Brython