DELETE + SETF inside a function

Question

I'm trying to write a function that will destructively remove N elements from a list and return them. The code I came up with (see below) looks fine, except the SETF is not working the way I intended.

(defun pick (n from)
  "Deletes (destructively) n random items from FROM list and returns them"
  (loop with removed = nil
     for i below (min n (length from)) do
       (let ((to-delete (alexandria:random-elt from)))
         (setf from (delete to-delete from :count 1 :test #'equal)
               removed (nconc removed (list to-delete))))
     finally (return removed)))

For most cases, this works just fine:

CL-USER> (defparameter foo (loop for i below 10 collect i))
CL-USER> (pick 3 foo)
(1 3 6)
CL-USER> foo
(0 2 4 5 7 8 9)
CL-USER> (pick 3 foo)
(8 7 0)
CL-USER> foo
(0 2 4 5 9)

As you can see, PICK works just fine (on SBCL) unless the element being picked happens to be the first on the list. In that case, it doesn't get deleted. That's because the only reassignment happening is the one that goes on inside DELETE. The SETF doesn't work properly (i.e. if I use REMOVE instead, FOO does not change at all).

Is there any scoping rule going on that I'm not aware of?

Answer 1

A (proper) list consists of cons cells that each hold a reference to the next cell. So, it is actually a chain of references, and your variable has a reference to the first cell. To make this clear, I rename the binding outside of your function to var:

var ---> [a|]--->[b|]--->[c|nil]

When you pass the value of the variable to your function, the parameter gets bound to the same reference.

var ---> [a|]--->[b|]--->[c|nil]
        /
from --'

You can update the references in the chain, for example eliminate b:

var ---> [a|]--->[c|nil]
        /
from --'

This has an effect on the list that var sees outside.

If you change the first reference, for example eliminating a, this is just the one originating from from:

var ---> [a|]--->[b|]--->[c|nil]
                /
        from --'

This has obviously no effect on what var sees.

You need to actually update the variable binding in question. You can do that by setting it to a value returned by function. Since you already return a different value, this would then be an additional return value.

(defun pick (n list)
  (;; … separate picked and rest, then
    (values picked rest)))

Which you then use like this, for example:

(let ((var (list 1 2 3)))
  (multiple-value-bind (picked rest) (pick 2 var)
    (setf var rest)
    (do-something-with picked var)))

Now to the separation: unless the list is prohibitively long, I'd stick to non-destructive operations. I also would not use random-elt, because it needs to traverse O(m) elements each time (m being the size of the list), resulting in a runtime of O(n·m).

You can get O(m) overall runtime by determining the current chance of picking the current item while linearly running over the list. You then collect the item into either the picked or rest list.

(defun pick (n list)
  (loop :for e :in list
        :and l :downfrom (length list)
        :when (or (zerop n)
                  (>= (random 1.0) (/ n l)))
            :collect e :into rest
          :else
            :collect e :into picked
            :and :do (decf n)
        :finally (return (values picked rest))))

Answer 2

Delete isn't required to modify any structure, it's just permitted to. In fact, you can't always do a destructive delete. If you wanted to delete 42 from (42), you'd need to return the empty list (), which is the symbol NIL, but there's no way that you can turn the list (42), which is a cons cell (42 . NIL) into a different type of object (the symbol NIL). As such, you'll probably need to return both the updated list, as well as the elements that were removed. You can do that with something like this, which returns multiple values:

(defun pick (n from)
  (do ((elements '()))
      ((or (endp from) (zerop n))
       (values elements from))
    (let ((element (alexandria:random-elt from)))
      (setf from (delete element from)
            elements (list* element elements))
      (decf n))))

CL-USER> (pick 3 (list 1 2 3 2 3 4 4 5 6))
(2 6 4)
(1 3 3 5)
CL-USER> (pick 3 (list 1 2 3 4 5 6 7))
(2 7 5)
(1 3 4 6)
CL-USER> (pick 2 (list 1 2 3))
(2 3)
(1)
CL-USER> (pick 2 (list 1))
(1)
NIL

On the receiving end, you'll want to use something like multiple-value-bind or multiple-value-setq:

(let ((from (list 1 2 3 4 5 6 7)))
  (multiple-value-bind (removed from)
      (pick 2 from)
    (format t "removed: ~a, from: ~a" removed from)))
; removed: (7 4), from: (1 2 3 5 6)

(let ((from (list 1 2 3 4 5 6 7))
      (removed '()))
  (multiple-value-setq (removed from) (pick 2 from))
  (format t "removed: ~a, from: ~a" removed from))
; removed: (3 5), from: (1 2 4 6 7)