list - Lisp S-表达式和列表长度/大小

Question

我正在尝试仅使用 Common Lisp 函数编写一个函数，该函数将计算一个 s 表达式中有多少个 s 表达式。例如:

((x = y)(z = 1)) ;; returns 2

和

((x - y)) ;; returns 1

嵌套表达式是可能的，所以:

((if x then (x = y)(z = w))) ;; returns 3

我写了一个函数来查找长度，如果没有嵌套表达式，它就可以工作。它是:

(define (length exp)
  (cond
    ((null? exp) 0)
    (#t (+ 1 (length (cdr exp))))))

现在我修改它以尝试支持以下嵌套表达式:

(define (length exp)
  (cond
    ((null? exp) 0)
    ((list? (car exp)) (+ 1 (length (cdr exp))))
    (#t (length (cdr exp)))))   

这适用于没有嵌套的表达式，但总是比嵌套表达式的答案小 1。这是因为以上面的例子为例，((if x then (x = y)(z = w)))，这将首先查看 if 并满足第三个条件，将 cdr(表达式的其余部分作为列表)返回到 length 中。在到达 (x=y) 之前会发生同样的情况，此时返回 +1。这意味着表达式 (if x then .... ) 没有被计算在内。

我可以用什么方式来解释它？添加 +2 将过度计算未嵌套的表达式。

我需要它在一个函数中工作，因为嵌套可以发生在任何地方，所以:

((x = y) (if y then (z = w)))

Answer 1

乍一看，您的代码只递归到右侧(cdr 端)而不是左侧(汽车端)，所以这肯定是个问题。

乍看之下，这甚至比那更棘手一点，因为您没有准确地计算 cons；您需要区分 cons 开始正确列表的情况与它是列表的 cdr 的情况。如果你要递归到汽车和 cdr，这些信息就会丢失。我们需要将 sexp 迭代为一个合适的列表，

(defun count-proper-list (sexp)
  (cond ((atom sexp) 0)
        (t (1+ (reduce #'+ (mapcar #'count-proper-list sexp))))))

但是这也会计算顶级列表，因此总是比你想要的多返回一个。所以也许，

(defun count-proper-sublist (sexp)
  (1- (count-proper-list sexp)))