Using Specter on tree data structures in Clojure
Tags: clojure, tree, algorithms, clojurescript
Published: 2020-11-02 07:08:20

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](https://github.com/ertugrulcetin/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](https://github.com/redplanetlabs/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;

```clojure
(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:

```clojure
(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.

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

```clojure
(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.

```clojure
(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;

```clojure
(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;

```clojure
(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.

```clojure
(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;

```clojure
(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.