-(defun butlast (x)
- (and (consp (cdr x))
- (cons (car x) (butlast (cdr x)))))
-
-(defun member (x list &key key (test #'eql testp) (test-not #'eql test-not-p))
+(defun butlast (x &optional (n 1))
+ "Returns x, less the n last elements in the list."
+ (nbutlast (copy-list x) n))
+
+(defun nbutlast (x &optional (n 1))
+ "Destructively returns x, less the n last elements in the list."
+ (cond
+ ((not (and (integerp n) (>= n 0)))
+ ;; TODO: turn this error into a type error, per CLHS spec.
+ (error "n must be a non-negative integer"))
+ ;; trivial optimizations
+ ((zerop n) x)
+ (t
+ ;; O(n) walk of the linked list, trimming out the link where appropriate
+ (let* ((head x)
+ (trailing (nthcdr n x)))
+ ;; If there are enough conses
+ (when (consp trailing)
+ (while (consp (cdr trailing))
+ (setq head (cdr head))
+ (setq trailing (cdr trailing)))
+ ;; snip
+ (rplacd head nil)
+ x)))))
+
+(defun member (x list &key key (test #'eql testp) (test-not #'eql test-not-p))