list - 为什么我的 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。 IE。 (空(CDR 列表))。

您的检查是检查前两个元素是否相同，而不是检查第一个元素和最后一个元素是否相同。

编辑

我能想到的使用递归而不使用反向的最佳方法是这样的:

(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