递归检查列表中的原子

Question

我正在尝试编写一个小型递归程序来测试列表并在每个元素都是原子时返回t。我遇到的问题是，当函数收到空列表时，它返回 t 而不是所需的 nil 结果。我无法想出一种方法让它返回 nil 对于最初的空列表，并且仍然以递归方式正常运行。

(defun only-atoms (in)
  (if (null in)
    t
    (and (atom (first in)) (only-atoms (cdr in)) )
  )
)

Answer 1

该函数可以在没有递归的情况下使用例如 every 来实现，如下所示：

(defun only-atoms (list)
  (and list (every #'atom list)))

当涉及到您所陈述的问题时，函数返回 T 而不是所需的 NIL 结果 当使用空列表调用函数时：

1. 如果 (null in) 为 true，则递归实现显式返回 T，这解释了您的发现。只需将其更改为所需的值NIL。考虑将 if 结构更改为 and。

2. 仅当列表有多个项目时才进行递归调用。对 (rest in) 进行适当的测试就可以了。如果列表位于最后一项，则提供真值而不是进行递归调用。

3. 仔细找到 only-atoms 调用以确保该函数可以尾递归。

例如：

    (defun only-atoms (list)
      (and list
          (atom (first list))
          (or (null (rest list))
              (only-atoms (rest list)))))

Answer 2

使用 COND，它允许您测试几种情况：

• 空列表 -> nil
• 一个元素列表 ->原子？ ;提示：不要使用 LENGTH
• else ->原子？对于第一个元素和其余元素的递归调用

Answer 3

空列表确实满足每个元素都是原子的条件！您要求它至少包含一个元素是一项附加要求。

表达“列表中的每个元素都是一个原子”的最简单方法是(every #'atom list)。您可以使用 和 将其与您的附加要求结合起来。

如果您坚持以 SICP 风格递归执行此操作，请将您的需求分开：

(defun not-empty-and-all-atoms (list)
  (and list
       (all-atoms list)))

(defun all-atoms (list)
  (if (endp list)
      t
      (and (atom (first list))
           (all-atoms (rest list)))))

Answer 4

这个解决方案工作正常：

(defun lat-p (lst)
           (labels ((lat-p* (lst) 
                      (cond
                       ((null lst) t)
                       ((atom (car lst)) (lat-p* (cdr lst)))
                       (t nil))))
             (if lst
                 (lat-p* lst)
                 nil)))

然而，一个更优雅的解决方案（没有递归）将是：

(defun lat-p (lst)
           (and lst (every #'atom lst)))

Answer 5

您可以将函数分成两部分，并在进入递归之前提供初始 nil 筛选。以下代码是这样做的一种方法（我试图使其尽可能接近提供的代码）：

(defun only-atoms (in)
  (defun only-atoms-iter (in)
    (if (null in)
        t
      (and (atom (first in)) (only-atoms-iter (cdr in)))))

  (unless (null in)
      (only-atoms-iter in)))

这也是使函数尾部递归的好机会：

(defun only-atoms (in)
  (defun only-atoms-iter (in state)
    (if (null in)
        state
      (only-atoms-iter (cdr in) (and state (atom (first in))))))

  (unless (null in)
      (only-atoms-iter in t)))