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 启动正确的列表与列表的 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)))