clojure - 来自 SICP 的 Clojure 中的 count-leaves

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 是递归的，因此没有提供真正的优势。