2

I'm having a problem with a little function that's supposed to count nodes and leaves in a tree. This is what it looks like:

(defn count-tree "Count nodes and leaves in a tree as produced by grow-tree-hlp." [tree] ; acc is [nodes leaves] (letfn [(inc-acc [x y] (map + x y))] (let [result (cond (leaf? tree) [0 1] ; increase leaves by 1 (node? tree) (reduce ; recurse over children while increasing nodes by 1 (fn [acc child] (inc-acc acc (count-tree child))) [1 0] (drop 2 tree)))] {:nodes (first result) :leaves (second result)})))

The error is:

(err) Execution error (ClassCastException) at screpl.core/count-tree (core.clj:282). (err) class clojure.lang.MapEntry cannot be cast to class java.lang.Number (clojure.lang.MapEntry is in unnamed module of loader 'app'; java.lang.Number is in module java.base of loader 'bootstrap')

I did a bit of testing, and it looks like the offending bits are (first result) and (second result) in the map that I want to return. The core of the function, the cond part, works just fine when it's taken out of let, the only problem is it returns a vector when I want a map.

Improve this question

3 Answers 3

Reset to default
5

The issue is that the inc-acc function expects two vectors of numbers (it's much better when things are documented BTW), but count-tree returns a map.

Few ways to fix it:

  • Use only vectors for both the acc and the result value of count-tree
  • Use only maps for those and adjust inc-acc
  • Change inc-acc so it accepts a vector and a map
  • Just write it all in a different way

Here's how I'd do it:

(def node? vector?) (def leaf? (complement node?)) (defn node-children [node] (drop 2 node)) (defn count-tree [tree] (letfn [(f [acc tree] (if (leaf? tree) (update acc :leaves inc) (reduce f (update acc :nodes inc) (node-children tree))))] (f {:nodes 0 :leaves 0} tree))) (count-tree [:div {} [:span {} "hello"] [:span {} "there"] [:div {} [:span {} "!"]]]) => {:nodes 5, :leaves 3}
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Of course! The calculation of result calls the entire count-tree, it's not contained within the let block, so it does matter what happens afer it. Thank you!
3

Eugene has explained the problem with your current approach and suggested a reasonable solution. I'd like to offer another, which takes advantage of Clojure's strength in producing and consuming lazy sequences. Instead of interleaving the logic for recursively consuming the tree with the logic for tabulating the results, split it into two parts:

  1. Consume the tree recursively, yielding a flat sequence describing the nodes and leaves
  2. Consume the sequence from (1), yielding a final result

I'll borrow Eugene's definitions of node?, leaf?, and node-children, which your question leaves unspecified.

(def node? vector?) (def leaf? (complement node?)) (defn node-children [node] (drop 2 node)) (defn node-stats [tree] (lazy-seq (if (leaf? tree) [{:leaves 1}] (cons {:nodes 1} (mapcat node-stats (node-children tree)))))) (defn count-tree [tree] (apply merge-with + {:nodes 0 :leaves 0} (node-stats tree)))

This produces the same result for Eugene's sample input, but I think it's a bit nicer, with the bookkeeping addition logic delegated to merge-with.

Improve this answer

Comments

3

If you know, how to determine a node (node?) and extract the children (node-children), there is tree-seq in cojure.core. With that, the counting can be done with reducing over the sequence.

(defn count-tree [tree] (reduce (fn [acc x] (update acc (if (node? x) :nodes :leaves) (fnil inc 0))) {} (tree-seq node? node-children tree)))
Improve this answer

3 Comments

tree-seq is a good tool for this. My nitpick would be that for a tree that's just a single leaf (or a single node with no children, if that's a thing that exists), your result map will be missing keys.
Right, of course. Thank you.
Good Point. Using an init argument in the proper shape for reduce instead of relying on fnil would mitigate that.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.