lisp - 如何在 Lisp Works 中对包含数字和字母的列表求和

Question

我正在尝试定义一个将列表作为参数的求和函数。问题是我的列表不仅可以包含数字，还可以包含字母。所以我的问题是，我怎样才能避开字母并继续验证列表的其余部分？

例子:(sum '(a 2 4 b d)) = 6

(defun sum (l) 
    ( if (numberp (CAR l)) (sum (CDR l)) (+ (CAR l) (sum (CDR l))) )
)

我只有一个“堆栈溢出”错误。

提前致谢。

Answer 1

您的代码尝试应用递归方法。在这里，格式正确，名称较长:

(defun sum (list) 
  (if (numberp (car list))
      (sum (cdr list))
      (+ (car list) (sum (cdr list)))))

你有堆栈溢出，因为当列表为空时你没有提供基本情况。如果将 NIL 列表传递给函数，会发生什么？

1. (car list) 返回 NIL，这不是一个数字。
2. 你去else分支。
3. 您尝试使用 (cdr list) 将 (car list) 添加到 SUM 的递归调用 中，它仍然是 NIL， 这也是 NIL。
4. 您回到了递归调用的第一步:无休止的递归，最终会触发错误，因为您在每次调用中不断分配堆栈帧。

因此，您必须定义给出空列表时会发生什么。这是一道典型的家庭作业题。我最喜欢的模板涉及 etypecase，因为它提供了一种防御性编码方法，可以及早拒绝错误并且对读者非常友好:

(defun foo (list)
  (etypecase list
    (null <base-case>)
    (cons <general-case>)))

但是，您也经常会发现这个，或者与 cond 等价的东西:

(defun foo (list)
  (if (null list)
      <base-case>
      <general-case>))

这可能是对学生的期望。更好的方法是使用 endp 而不是 null，因为前者会检查参数是否实际上是一个列表。

在你的问题中:

• 基本情况显然返回 0。
• 一般情况下计算 car 的总和(如果不是数字则为零)与递归获得的 cdr 的总和。

但是，你将有一个递归函数需要将中间结果存储在调用堆栈上，这是一种浪费。为了拥有尾递归函数，您需要将结果总和作为函数的参数传递:首先传递 0，然后每个递归调用首先计算总和，然后再递归调用自身。基本情况返回总和。这保证了递归调用之间不需要存储中间结果，在适当的情况下(这取决于您的实现)可以作为循环进行优化。但是由于 Common Lisp 已经提供了迭代结构，你应该在实践中使用它们:

(loop for e in list when (numberp e) sum e)

如果您对高阶函数感兴趣，下面的方法也可以，但会分配一个中间列表(这是否可以接受取决于列表的预期大小):

(reduce #'+ (remove-if-not #'numberp list))