为什么我口齿不清函数返回“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))。

的检查你有检查，如果两个第一要素是相同的，而不是如果第一个和最后一个要素是相同的。

编辑

用递归和不使用反向，我能想到的做到这一点，最好的办法是这样的：

(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