为什么我的 lisp 函数返回 'NIL'

Question

我正在编写一个 lisp 函数，它将在不使用 'reverse' 函数的情况下确定一个单词是否为回文。我是 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

我怎么看它似乎适用于一组特殊的回文，其中有偶数个相同类型的元素。

对于一个元素列表，您需要 return t。 IE。 (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 从头到尾制作列表，因此历史是所有看到的元素的倒序，因此当您到达中间时应该匹配尾部。当hare的cdr或cddr为null时，你在中间，可以通过简单的比较来确定回文。

编辑 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

为什么我的 lisp 函数返回 'NIL'

Why is my lisp function returning 'NIL'

lisp

clisp

list

common-lisp