count-leaves in Clojure from SICP

Question

I'm going over SICP translating problems into Clojure to learn both Clojure and read SICP. Currently, I am stuck with the Count Leaves procedure from Section 2.2.2.

The goal is to write a function that takes a list representation of a tree, e.g. '(1 2 '(3 4)) and counts the number of leaves, in this case 4.

So far, the closest I have come up with is

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

However, this does not handle subtrees correctly. In particular, it evaluates

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

to 2 instead of 1.

Note the Scheme implementation from the book is:

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

Answer 1

Comment

As @jkiski's comment suggests, your code works. So there is no problem.

But I'd prefer to test whether the argument is a sequence first. Try working out how (count-leaves '()) evaluates to 0!

Switch the first two clauses of the cond and we get ...

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

... where I've used rest instead of the next implicit in the destructuring, so empty? instead of nil? to test it. This deals properly with nil values, which your code doesn't. But it is still properly recursive, so remains subject to stack overflow.

I prefer ...

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

... which is still recursive, but cleaner.

---

Edit

I've had to retract my good opinion of @glts's solution: postwalk is recursive, so offers no real advantage.

Answer 2

Translating examples from one language into another is a good exercise, but do keep in mind that a language also comes with its own idiom, and its own core library.

In Clojure, walking data structures is especially easy with clojure.walk.

After requiring clojure.walk you can run postwalk-demo to see how your data structure is traversed:

(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))

Then you can devise a function to count the leaf nodes and pass it to postwalk.

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

During the postwalk traversal leaf nodes get replaced with 1, and seqs get replaced with the sum of their constituent leaf counts.

I realise that this is a tangential answer but perhaps you still find it useful!