Почему моя функция lisp возвращает «NIL»

Question

Я пишу функцию lisp, которая определит, является ли слово палиндром без использования функции «обратного». Я довольно новичок в lisp, и я все еще пытаюсь понять концепцию. Функция возвращает NIL каждый раз, когда я тестирую палиндром, любые идеи почему?

Моя функция Я придумал.

(defun palindromep (list) 
    (cond 
     ((null list)t) 
     (t 
      (and (equal (first list) (first (rest list))) 
       (palindromep (butlast (rest list))))))) 

редакция Код

(defun palindromep (list) 
    (cond 
     ((null list)t) 
     (t 
      (and (equal (first list) (first(last list))) 
       (palindromep (butlast(rest list))))))) 

Answer 1

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

Для одного списка элементов вам необходимо вернуть t. то есть. (null (cdr list)).

Проверьте, есть ли у вас чеки, если два первых элемента одинаковы, если первый и последний элементы одинаковы.

EDIT

Лучший способ сделать это с помощью рекурсии и без использования обратного, что я могу думать так:

(defun palindromep (list) 
    (labels ((aux (history tortoise hare) 
      (cond ((null hare) (equal tortoise history)) 
        ((null (cdr hare)) (equal (cdr tortoise) history)) 
        (t (aux (cons (car tortoise) history) 
          (cdr tortoise) 
          (cddr hare)))))) 
    (aux '() list list))) 

Как это работает, имея дополнительный курсор hare что итерации удваивает расстояние как tortoise, и в то же время видимый элемент накапливается в history. Поскольку cons делает списки от конца до начала истории, все видимые элементы в обратном направлении и, следовательно, должны совпадать с окончанием, когда вы достигли середины. Когда либо cdr, либо cddr зайца является нулевым, вы находитесь посередине и можете легко определить палиндром.

EDIT 2

При перемещении помощника из его легче отслеживать и увидеть, что происходит:

(defun aux (history tortoise hare) 
    (cond ((null hare) (equal tortoise history)) 
     ((null (cdr hare)) (equal (cdr tortoise) history)) 
     (t (aux (cons (car tortoise) history) 
       (cdr tortoise) 
       (cddr hare))))) 

(defun palindromep (list) 
    ;; just calls helper 
    (aux '() list list)) 

;; trace the helper 
(trace aux) 
(trace equal) ; you might need to follow instructions to unlock 

(palindromep '(1 2 3 3 2 1)) 
    0: (AUX NIL (1 2 3 3 2 1) (1 2 3 3 2 1)) 
    1: (AUX (1) (2 3 3 2 1) (3 3 2 1)) 
     2: (AUX (2 1) (3 3 2 1) (2 1)) 
     3: (AUX (3 2 1) (3 2 1) NIL) 
      4: (EQUAL (3 2 1) (3 2 1)) 
      4: EQUAL returned T 
     3: AUX returned T 
     2: AUX returned T 
    1: AUX returned T 
    0: AUX returned T 
==> T 

(palindromep '(1 2 3 4 5 6)) 
    0: (AUX NIL (1 2 3 4 5 6) (1 2 3 4 5 6)) 
    1: (AUX (1) (2 3 4 5 6) (3 4 5 6)) 
     2: (AUX (2 1) (3 4 5 6) (5 6)) 
     3: (AUX (3 2 1) (4 5 6) NIL) 
      4: (EQUAL (4 5 6) (3 2 1)) 
      4: EQUAL returned NIL 
     3: AUX returned NIL 
     2: AUX returned NIL 
    1: AUX returned NIL 
    0: AUX returned NIL 
==> NIL