是否有一个常见的lisp宏用于从列表中弹出第n个元素？

Question

我对Common Lisp场景很新鲜,我似乎无法找到一个快速的方法从列表中获取第n个元素并同时从列表中删除它.我已经完成了,但它并不漂亮,我真正喜欢的是像"pop"这样的东西,但又采用了第二个参数:

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

我很确定"popnth"必须是一个宏,以防参数为0并且它必须表现得像"pop".

编辑:这是我的垃圾第一版:

(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))))

Answer 1

像这样的东西:

删除列表的第n个元素:

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

不断返回一个函数,它总是返回它的参数.

作为接受地点的宏,使用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)))))

示例:

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)

Answer 2

是的,Lisp有一个用于弹出列表第N个元素的宏:它被调用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 适用于任何表示场所的形式.

问题是,不像cddr,nthcdr是不是访问; 像(nthcdr 3 list)不表示某个地方的形式; 它只能作为函数调用.

写一种特殊的形式pop并不是最好的答案; 相反,我们可以通过编写一个nthcdr行为类似于地点访问器的克隆来实现更一般的修复.然后pop宏将工作,所有其他宏将与像setf和的地方一起工作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)))))

测试:

$ 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]> 

对实现的一种可能的改进是分析idx表单并优化掉生成的代码,该代码实现对值的运行时检查idx.也就是说,如果idx是常量表达式,则不需要发出测试是否idx为零的代码.可以发出适当的代码变体.不仅如此,但对于小的值idx,该代码可以发出基于"尸体"的特殊变种:cddr,cdddr,而不是一般nthcdr.但是,其中一些优化可能由Lisp编译器完成,因此是多余的.

Answer 3

我想出了一个比我第一次尝试更有效的解决方案：

(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))))

这是它的实际效果：

[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)