Почему я не могу удалить текущий элемент при переборе списка?

Question

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

 (defun foo (list action test)
   (do ((elt (car list) (car list)))
       ((null list))
     (funcall action elt)
     (when (funcall test elt)
       (delete elt list))))

(setq list '(1 2 3 4))
(foo list #'pprint #'oddp)
-> infinite loop

Разве это невозможно, так как оно указывает на себя?В конце концов, elt - это, конечно, (car list).

Это правильная оценка?И как я мог решить это эффективно?

Answer 1

Цикл бесконечен, так как вы ничего не повторяете, вы несколько раз применяете action, но если он не мутирует элемент, как это делает pprint, тогда, если результат test отрицательным, то он останется таким, и список не будет пустым, даже если удаление сработало при вашей попытке.

УДАЛИТЬ является деструктивной функцией. В Common Lisp деструктивным операциям разрешено уничтожать их аргументы. Вы должны отказаться от любых ссылок на аргумент и использовать только возвращаемое значение. После завершения операции нет никаких гарантий относительно состояния аргумента. В частности, это может не иметь никакого эффекта, поскольку реализациям также разрешается действовать идентично неразрушающему аналогу, но обычно составные части последовательности будут повторно собираться некоторым трудным для прогнозирования способом. В вашем примере вы также уничтожаете литерал с неопределенным поведением, которого следует избегать.

Как правило, лучше всего рассматривать списки в Common Lisp как неизменяемые и разрушительные операции как микрооптимизацию, которую следует использовать только тогда, когда вы уверены, что они ничего не сломают. Для этой проблемы вы можете перебрать список, используя LOOP, собирая список результатов с условным значением COLLECT. См. Главу LOOP в PCL .

Answer 2

На самом деле вы можете изменять состояние своего списка, перебирая его. Вам просто нужно будет использовать rplacd в дополнение к delete и управлять продвижением по списку не в предложении итерации, а внутри тела do:

 (defun nfoo (lst action test)
   (do* ((list (cons 1 lst))
         (elt (cadr list) (cadr list)))
        ((null (cdr list))
         (if (funcall test (car lst)) (cdr lst) lst))
     (funcall action elt)
     (if (funcall test elt)
       (rplacd list (delete elt (cddr list)))
       (setf list (cdr list)))))  

Вы должны вызывать его через copy-list, если не хотите, чтобы он уничтожал список аргументов.

Если вы хотите удалить из списка не все элементы, равные elt, которые прошли тест, а скорее все такие, что будет проходить тест, то вызов delete должен быть передал функцию test в качестве аргумента :test.

( edit: ) и даже намного проще и понятнее, как эта ( неразрушающая ) версия:

(defun foo (list action test)
   (do* ((elt (car list) (car list)))
        ((null list))
     (funcall action elt)
     (if (funcall test elt)
       (setf list (delete elt list))
       (setf list (cdr list)))))

Answer 3

Я немного новичок в Лиспе, так что, возможно, я что-то упустил в вашем вопросе.Тем не менее, я думаю Я понимаю, что вы спрашиваете, и мне интересно, почему вы не используете некоторые существующие структуры для этого ... а именно remove-if-not (или remove-if, если у меня есть вещи назад)и mapcar ...

(mapcar #'pprint (remove-if-not #'oddp '(1 2 3 4))

Вышеприведенные отпечатки 1 и 3 (и возвращает (nil nil), но, вероятно, вы можете игнорировать это ... или вы можете выполнить defun, который делаетвыше и заканчивается (values)).(Если вам нужны вечера, измените remove-if-not на remove-if.)

Мне кажется, что это может быть более разумный путь, если вы не делаете это по педагогическим причинам или яупустить что-то ... любое из которых я признаю, вполне возможно.:)

PS Гиперспец информация о remove-if, remove-if-not и т. Д.