DELETE + SETF внутри функции

Question

Я пытаюсь написать функцию, которая разрушительно удалит N элементов из списка и вернет их. Код, который я придумал (см. Ниже), выглядит отлично, за исключением того, что SETF работает не так, как я предполагал.

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

В большинстве случаев это работает просто отлично:

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) 

Как вы можете видеть, PICK работает просто отлично (на SBCL), если элемент быть выбранным не случается, первым в списке. В этом случае он не удаляется. Это потому, что единственное повторное назначение - это то, что происходит внутри DELETE. SETF не работает должным образом (т. Е. Если я использую REMOVE, то FOO не изменяется вообще).

Существует ли какое-либо правило определения, о котором я не знаю?

Answer 1

Список (соответствующий) состоит из cons-ячеек, в каждом из которых содержится ссылка на следующую ячейку .Таким образом, это фактически цепочка ссылок, и ваша переменная имеет ссылку на первую ячейку. Чтобы пояснить это, я переименовать связывающую вне вашей функции var:

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

Когда вы передаете значение переменной вашей функции, параметр получает , связанный с той же ссылкой.

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

Вы можете обновить ссылки в цепи, например, устранить b:

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

Это оказывает влияние на список, который var видит снаружи.

Если изменить первую ссылку, например, устраняя a, это только один происходящий из from:

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

Это не имеет, очевидно, не влияет на то, что var видит.

Необходимо на самом деле обновить привязку переменной в вопросе. Вы можете сделать это , установив его на значение, возвращаемое функцией. Поскольку вы уже возвращаете значение , это будет дополнительным возвращаемым значением.

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

который затем использовать, как это, например:

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

Теперь к отделению: если список не будет чрезмерно долго, я бы придерживаться неразрушающих операций. Я также не буду использовать random-elt, поскольку ему необходимо пересечь O (M) элементов каждый раз (м являющихся размер списка), в результате чего времени выполнения O (N & Мидот; м).

Вы можете получить O (м) общее время выполнения определения текущего шанс выбора текущего пункта в то время как линейно работает над списком. Затем вы берете элемент либо в выбранный, либо в список отдыха.

(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 необязательно изменяет свой аргумент последовательности. Как hyperspec говорит:

delete, delete-if и delete-if-not возвращает последовательность того же типа, что и последовательности, которая имеет те же элементы, за исключением, что те, в подпоследовательности ограниченной start и end и удовлетворяющих тесты были удалены. Последовательность может быть уничтожена и использована для построения результата; однако результат может быть или не быть идентичным последовательности.

Например, в SBCL:

* (defvar f (loop for i below 10 collect i)) 

F 
* (defvar g (delete 0 f :count 1 :test #'equal)) 

G 
* g 

(1 2 3 4 5 6 7 8 9) 

* f 

(0 1 2 3 4 5 6 7 8 9) 
* 

Обратите внимание, что в функции setf изменяет локальную переменную from, и так как delete в случае первого элемента не изменяет первоначальный список, в конце функции переменная foo поддерживает старые значения.

Answer 3

Удалить не для изменения любой структуры, это всего лишь разрешено. На самом деле вы не всегда можете сделать деструктивное удаление. Если вы хотите удалить 42 из (42), вам нужно будет вернуть пустой список(), который является символом NIL, но вы не можете повернуть список (42), который является ячейкой cons (42) NIL) в другой тип объекта (символ NIL). Таким образом, вам, вероятно, потребуется вернуть как обновленный список, так и удаленные элементы. Вы можете сделать это с чем-то вроде этого, который возвращает несколько значений:

(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 

На приемном конце, вы будете хотеть использовать что-то вроде множественного значения-привязки или множественного значения -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)