Warum gibt meine Lisp-Funktion 'NIL' zurück

Question

Ich schreibe eine Lisp-Funktion, die bestimmt, ob ein Wort ein Palindrom ist, ohne die Funktion 'reverse' zu verwenden. Ich bin ziemlich neu zu Lispeln und ich versuche immer noch, das Konzept zu begreifen. Die Funktion gibt NIL jedes Mal, wenn ich ein Palindrom testen, irgendwelche Ideen warum?

Meine Funktion habe ich mir ausgedacht. ein ein spezieller Satz von Palindrome zu arbeiten, wo es gerade Anzahl von Elementen der gleichen Art

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

-Code Revision

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

Answer 1

Wie ich es sehe es scheint.

Sie müssen t für eine Elementliste zurückgeben. dh. (null (cdr list)).

Die Prüfung, die Sie überprüfen, ob die beiden ersten Elemente identisch sind, wenn das erste und das letzte Element identisch sind.

EDIT

Der beste Weg, dies mit Rekursion zu tun und ohne umkehren mit, dass ich denken kann, ist auf diese Weise:

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

Wie es funktioniert, ist eine zusätzliche Cursor, indem hare dass Iteriert die doppelte Distanz wie die tortoise und gleichzeitig wird das gesehene Element in history akkumuliert. Da Listen von Ende zu Anfang erstellt, ist die Geschichte alle gesehenen Elemente in umgekehrter Reihenfolge und sollte daher dem Ende entsprechen, wenn Sie die Mitte erreicht haben. Wenn entweder cdr oder cddr von Hase Null ist, sind Sie in der Mitte und können Palindrom durch einen einfachen Vergleich ermitteln.

EDIT 2

Wenn Sie bewegen, um den Helfer heraus, dass es einfacher ist, zu verfolgen und sehen, was geschieht:

(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