Using Specter on tree data structures in Clojure

Ertuğrul Çetin — Mon, 02 Nov 2020 07:08:20 +0000

Creating visual apps has always been fun, and I was considering to build one that I could enjoy. After some digging, I decided to make a mind mapping tool for myself. Since I recently wrote a simple ClojureScript wrapper for KonvaJS konva-cljs, I was like, that should be a great fit!

If you take a closer look, you'll immediately see that a mind mapping structure is a tree data structure. Meaning I have to deal with deeply nested structures and need the right tool for the job; the first thing that comes to mind is the spectacular library called Specter.

Without further ado, let's check some code. (Code samples provided from the project)

One of the CRUD functions was finding a node by id, so I come up with this;

(require '[com.rpl.specter :as s])

(defn find-node-by-id [tree id]
  (s/select-first (s/walker #(= id (:id %))) tree))

walker executes a depth first search for nodes where pred function returns a truthy value. When pred returns a truthy value, walker stops searching that branch of the tree and continues its search of the rest of the data structure.

Since every node has a unique id attribute, we can select the first one using select-first macro.

Also, I needed to find the parent node by child id:

(defn find-parent-by-child-id [tree child-id]
  (s/select-first
   (s/walker
    (fn [node]
      ((set (map :id (:children node))) child-id)))
   tree))

At some point, I need to find nodes at the same level.

(defn find-same-level-nodes [tree node-id]
  (let [parent (find-parent-by-child-id tree node-id)]
    (if (:root? parent)
      (:children parent)
      (->> parent
           :id
           (find-parent-by-child-id tree)
           :children
           (mapcat :children)))))

Let's remove and update some nodes in the tree. Before doing that, we could define a recursive-path to traverse the tree. (Another approach)

(def MAP-NODES
  (s/recursive-path [] p
    (s/cond-path
      sequential? (s/continue-then-stay s/ALL p)
      map? (s/continue-then-stay s/MAP-VALS p))))

If Specter comes across data which is sequential or map, it will recursively go into the data search for MAP-VALS. (We could have also used coll? only)

Alright, after defining this crucial path, let's add some nodes.

(defn add-node [tree parent-id node id]
  (let [node (assoc node :id id :h shape-h :w shape-w)
        tree (s/transform [q/MAP-NODES #(= parent-id (:id %)) :children]
                          #((fnil conj []) % node)
                          tree)]
    (update-positions tree parent-id id)))

add-node traverses the tree with MAP-NODES, and if it finds the given parent-id, provided node will be added into :children.

Removal operation;

(defn remove-node-by-id [tree id]
  (s/setval [MAP-NODES #(= id (:id %))] s/NONE tree))

In here, removing the node by using setval macro.

An update is also similar;

(defn update-node-by-id [tree id update-fn]
  (s/transform [MAP-NODES #(= id (:id %))] update-fn tree))

I used transform instead of setval due to the update function.

Let's update all nested children by parent id. First, let's create a function that gets all nodes.

(defn- traverse [node]
  (when (-> node :children seq)
    (lazy-cat (:children node) (map traverse (:children node)))))

(defn get-nodes [root]
  (->> root
       (traverse)
       (cons root)
       (flatten)
       (remove nil?)))

Now we can apply the update operation to all children;

(defn update-children-by-parent-id [tree parent-id update-fn]
  (let [parent   (find-node-by-id tree parent-id)
        children (set (map :id (rest (get-nodes parent))))]
    (s/transform [MAP-NODES #(children (:id %))] update-fn tree)))

I don't want to keep the post too long. I think you got the whole picture.

Long story short, Specter is powerful and fun to work with. It's enabling to solve fairly complex problems with well-structured abstractions.

I'd highly recommend it if you have a similar use case just like I had.

DEV Community: Ertuğrul Çetin

Using Specter on tree data structures in Clojure