clojuretree-traversal

Converting a vector to a map in Clojure


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.


Solution

  • 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:

    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}