clojure - 来自 SICP 的 Clojure 中的计数叶

Question

我将通过 SICP 将问题转化为 Clojure，以学习 Clojure 和阅读 SICP。目前，我坚持使用第 2.2.2 节中的计算叶子过程。

目标是编写一个函数，该函数采用树的列表表示形式，例如'(1 2 '(3 4)) 并计算叶子的数量，在本例中为 4。

到目前为止，我想到的最接近的是

(defn count-leaves
  [coll]
  (cond
    (nil? coll) 0
    (not (seq? coll)) 1
    :else (let [[left & right] coll] (+ (count-leaves left) (count-leaves right)))
    ))

但是，这并不能正确处理子树。特别是，它评估

(count-leaves '('(1)))

到 2 而不是 1。

注意方案实现from the book是:

(define (count-leaves x)
  (cond ((null? x) 0)
        ((not (pair? x)) 1)
        (else (+ (count-leaves (car x))
                 (count-leaves (cdr x))))))

Answer 1

评论

正如@jkiski 的评论所暗示的那样，您的代码有效。所以没有问题。

但我更愿意先测试参数是否是一个序列。尝试找出 (count-leaves '()) 的计算结果如何为 0!

交换 cond 的前两个子句，我们得到 ...

(defn count-leaves [coll]
  (cond
    (not (seq? coll)) 1
    (empty? coll) 0
    :else (+ (count-leaves (first coll)) (count-leaves (rest coll)))))

... 我使用 rest 而不是解构中隐含的 next 的地方，所以 empty? 而不是 nil? 来测试它。这可以正确处理 nil 值，而您的代码不会。但它仍然是正确递归的，因此仍然容易发生堆栈溢出。

我更喜欢...

(defn count-leaves [coll]
  (if (seq? coll)
    (apply + (map count-leaves coll))
    1))

...这仍然是递归的，但更清晰。

---

编辑

我不得不收回对 @glts's solution 的好感: postwalk 是递归的，所以没有真正的优势。