Pourquoi ma fonction lisp retourne-t-elle 'NIL'

Question

J'écris une fonction lisp, qui va déterminer si un mot est un palindrome sans utiliser la fonction 'reverse'. Je suis assez nouveau à lisp et j'essaye toujours de saisir le concept. La fonction renvoie NIL chaque fois que je teste un palindrome, des idées pourquoi?

Ma fonction est née.

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

Code de révision

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

Answer 1

Comment je vois cela semble fonctionner un un ensemble spécial de palindromes où il y a même nombre d'éléments du même genre.

Vous devez renvoyer t pour la liste d'un élément. c'est à dire. (null (cdr list)).

La vérification que vous avez vérifie si les deux premiers éléments sont identiques si le premier et le dernier élément sont identiques.

EDIT

La meilleure façon de le faire avec récursivité et sans utilisation de l'inversion que je peux penser est ainsi:

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

Comment ça marche est en ayant un curseur supplémentaire hare que itère deux fois la distance en tant que tortoise et en même temps l'élément vu est accumulé en history. Depuis cons fait des listes de bout en bout l'histoire est tous les éléments vus en sens inverse et devrait donc correspondre à la fin lorsque vous avez atteint le milieu. Quand ou cddr de hare est nul, vous êtes au milieu et pouvez déterminer palindrome par une comparaison facile.

EDIT 2

Si vous déplacez l'aide sur il est plus facile de retracer et de voir ce qui se passe:

(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