来自 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

将示例从一种语言翻译成另一种语言是一个很好的练习，但请记住，一种语言也有自己的习惯用法和自己的核心库。

在 Clojure 中，使用 clojure.walk 遍历数据结构特别容易。

要求 clojure.walk 之后，您可以运行 postwalk-demo 查看您的数据结构是如何遍历的：

(require '[clojure.walk :refer [postwalk postwalk-demo]])
(postwalk-demo '(1 2 (3 4)))

Walked: 1
Walked: 2
Walked: 3
Walked: 4
Walked: (3 4)
Walked: (1 2 (3 4))

然后你可以设计一个函数来计算叶节点并将其传递给postwalk。

(postwalk (fn [e]
            (if (seq? e) (apply + e) 1))
          '(1 2 (3 4)))

在 postwalk 遍历期间，叶子节点被替换为 1，seqs 被替换为组成叶子计数的总和。

我知道这是一个切题的答案，但也许您仍然觉得它有用！

Answer 2

正如@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))

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

编辑

我不得不收回我对的好感：postwalk 是递归的，因此没有真正的优势。

来自 SICP 的 Clojure 中的计数叶

count-leaves in Clojure from SICP

lisp

clojure

sicp