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.