Понимание хвоста в Common Lisp

Question

Просматривая «Краткий справочник по Common Lisp» Берта Бургемайстера, я наткнулся на tailp.

Во-первых, я неправильно понял определения этой функции.И я попытался:

(tailp '(3 4 5) '(1 2 3 4 5))

Но он вернул

NIL

CLTL2 говорит, tailp верно тогда первый аргумент - любой (nthcdr n list) с существующимn.

(nthcdr 2 '(1 2 3 4 5))
;; (3 4 5)

Я также пытался:

(tailp '(3 4 5) '(1 2 3 4 5))
;; NIL - and I would expect: T following the definition above.

(tailp '() '(1 2 3 4 5))
;; T
(tailp '5  '(1 2 3 4 . 5))
;; T

Пока я не попытался (а затем понял, tailp ищет cdr из l, которые имеют даже тот же адрес.

(defparameter l '(1 2 3 4 5 6))
(tailp (nthcdr 3 l) l)
;; T

Но тогда у меня возник следующий вопрос:

For what such a function is useful at all?

Не будет ли функция более полезной, которая проверяет, является ли подсписок частью alist? (Или выглядиткак часть списка, вместо этого он должен иметь один и тот же адрес?)

Замечание:

Ну ладно, постепенно я начинаю понимать, что, может быть, это что-то вродеeq для cdr частей списка ... Вид ... "Любой cdr - производный от указанного списка eq до первого аргумента?".

Но, может быть, кто-томожете мне объяснить, в каких ситуациях такой тест очень полезен?

Answer 1

Вот случай, когда tailp полезен:

(defun circular-list-p (l)
  (and (consp l)
       (tailp l (rest l))))

Пара примечаний.

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

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

Answer 2

Я почти уверен, что ответ на (tailp '(3 4 5) '(1 2 3 4 5)) может быть как t, так и nil, как умный компилятор может сделать (tailp '#1=#(3 4 5) '(1 2 . #1#)), чтобы уменьшить объем используемой памяти.Цитируемые вещи являются неизменяемыми литералами, так почему бы не использовать одну и ту же память дважды?

Вот как работает tailp:

(defparameter *tail* (list 3 4 5))
(defparameter *larger* (list* 1 2 *tail*))
(defparameter *replica* (copy-list *larger*))

(tailp *tail* *replica*) ; ==> nil
(tailp *tail* *larger*)  ; ==> t

Поскольку copy-list создает новые минусы для каждого элемента вlist, он будет делиться только пустым списком с любым другим списком.Он уникален.

*larger* был сделан с общим хвостом с *tail*, и поэтому (tailp *tail* *larger*) будет t.

Важно, чтобы он сравнивал аргументы одинаковообъекты.Поскольку хвост не должен быть списком, он сравнивается с eql.При сравнении, если вещи выглядят одинаково, вы используете equal, поэтому tailp более конкретно, чем это.Указатель должен быть равен (eq) или eql атомному значению.

Так где вы это используете?Я имею в виду функциональную структуру данных, в которой вы обычно используете общую структуру.tailp может использоваться для идентификации поддерева родителя.Это в основном более производительная версия этого:

(defun my-tailp (needle haystack)
  (cond ((eql needle haystack) t)
        ((atom haystack) nil)
        (t (my-tailp needle (cdr haystack)))))

Answer 3

@ Sylwester:

Спасибо, @Sylwester!

Я недавно прочитал в книге Эди Вейц о том, как хвост машет списком:

(defparameter *list* (list 'a 'b 'c 'd))
(defparameter *tail* (cdddr *list*))

Это название машины последней противоборствующей ячейки списка, как *tail* - и теперьдобавьте к нему новый элемент и переименуйте новую последнюю машину в последнюю ячейку cons списка *tail*.

(setf (cdr *tail*) (cons 'e 'nil) 
      *tail*       (cdr *tail*)) 
;; (E)

Теперь список:

*list* 
;; (A B C D E) 

, и можно добавить через setf дополнительные элементы к *tail* без необходимости повторного просмотра списка.(Так улучшается производительность. Но с предупреждением, конечно, потому что это разрушительное действие).

Возможно, если бы кто-то назвал список, как вы сделали:

(defparameter *my-new-tail* '(F G H))

и tail wagg это до конца нового списка

(setf (cdr *tail*) *my-new-tail*
      *tail* (cddr *my-new-tail*))

А-а или альтернативно:

(defparameter *tail-of-my-new-tail* (cddr *my-new-tail*))
;; and then
(setf (cdr *tail*) *my-new-tail*
      *tail*       *tail-of-my-new-tail*)

Тогда

(tailp *my-new-tail* *list*)

• будет проверкой, будет лиэта процедура была выполнена правильно
• также будет проверкой, был ли я добавлен новый хвост в дополнение к *my-new-tail* или нет, или если *my-new-tail* был последним хвостом, который был вилял до *list* илине ...
• , поэтому tailp было бы весьма полезным тестом в контексте хвостового виляния ...
• или, как вы сказали, если реализация использует хвостовое виляние из соображений производительности(и, возможно, постоянно отслеживая хвосты списков), в этом контексте реализация может использовать tailp в качестве теста, вносит ли данный список вклад в другой список в качестве недавно добавленного хвоста ...

Это только что пришло мне в голову, когда я читалВаш ответ, @Sylwester!(Я не осознавал этого, когда читал о том, как вилять хвостом в книге - (что, кстати, очень полезно!) Спасибо, что ответили!

Answer 4

Основная цель tailp - проверить, существует ли общая структура списка.Это означает, что cons-ячейки одинаковы (что означает EQL в качестве предиката), а не только содержимое cons-ячеек.

Можно также проверить, находится ли элемент впоследний cdr:

CL-USER 87 > (tailp t '(1 2 3 4 . t))
T

CL-USER 88 > (tailp nil '(1 2 3 4 . nil))
T

CL-USER 89 > (tailp nil '(1 2 3 4))
T

CL-USER 90 > (tailp #1="e" '(1 2 3 4 . #1#))
T

Это одна из редко используемых функций в Common Lisp.