在Lisp中进行递归的回文检查

Question

我已经开发了代码来检查输入内容以查看它是否是回文，但是我很难弄清楚如何打印输出。如果输入是回文，我希望输出返回“ t”，否则返回“ nil”。我想给自己的另一个挑战是不使用反向函数，这就是为什么我的代码不那么简单的原因。预先感谢。

(defun palindromep(l)
  (cond ((null l) nil (write nil))
        (t (append (list (car l)) (palindromep (cdr l)) (list (car l) )))))


        (palindromep '(a b b a))
        (terpri)
        (palindromep '(a b c b a))
        (terpri)
        (palindromep '(a b c))
        (terpri)
        (palindromep '(a (d e) (d e) a))
        (terpri)
        (palindromep '(a (d e) (e d) a))

Answer 1

首先，空白列表是回文！如果我们将其反转，则会得到相同的空列表。

第二，Lisp函数不打印其结果值；他们返回这些值。

在交互式会话中，是由侦听器打印从要求值的表达式中出现的结果值。该表达式本身不必打印任何内容。

因此，我们开始这样：

(defun palindromep (l)
  (cond
    ((null l) t) ;; the empty list is a palindrome: yield true.

请注意，如果我们这样写：

    ((null l) nil t) ;; the empty list is a palindrome: yield true.

没有任何作用。计算多余的nil表达式，产生nil，将其丢弃。 Lisp编译器将完全消除该问题。

如果列表根本不是列表，而是nil以外的原子怎么办？让我们将其视为回文。不过，需要澄清要求：

    ((atom l) t)

现在我们知道我们正在处理一个非空列表。如果它只有一项，那就是回文：

    ((null (cdr l)) t)

现在我们知道我们正在处理两个或多个项目的列表。如果第一个和最后一个项目相同，并且它们之间的项目形成回文，那就是回文。

    (t (let* ((first (car l))
              (rest (cdr l))
              (tail (last l))
              (interior (ldiff rest tail)))
         (and (eql first (car tail)) (palindromep interior))))))
整个事情：

(defun palindromep (l)
  (cond
    ((null l) t)
    ((atom l) t)
    ((null (cdr l)) t)
    (t (let* ((first (car l))
              (rest (cdr l))
              (tail (last l))
              (interior (ldiff rest tail)))
         (and (eql first (car tail)) (palindromep interior))))))
代码打高尔夫球：在ANSI CL描述的cond构造中，子句只允许采用一种形式。如果以这种形式产生真值，则返回该值。这样我们就可以删除t了：

(defun palindromep (l)
  (cond
    ((null l))        ;; t removed
    ((atom l))        ;; likewise
    ((null (cdr l)))  ;; likewise
    (t (let* ((first (car l))
              (rest (cdr l))
              (tail (last l))
              (interior (ldiff rest tail)))
         (and (eql first (car tail)) (palindromep interior))))))
关于功能ldiff和last的文档可以是found here。

[进一步打高尔夫球：如果我们使用此模式(cond (A) (B) ... (t Z))，我们可以将其替换为(or A B ... Z)：

(defun palindromep (l)
  (or (null l)
      (atom l)
      (let* ((first (car l))
             (rest (cdr l))
             (tail (last l))
             (interior (ldiff rest tail)))
        (and (eql first (car tail)) (palindromep interior)))))
[cond就像是or的概括，可以为每个终止的真实情况指定替代结果值。

Answer 2

继续进行代码查询，因为期望使用t或nil，所以只能使用or和nil表示条件（并且使用or和nil表达式的短路）。

Answer 3

只是为了完成其他答案，我想指出的是，不使用reverse不仅会极大地使您的代码复杂化，而且会使效率大大降低。只需将以上答案与经典答案进行比较：