Logo

dev-resources.site

for different kinds of informations.

Using Specter on tree data structures in Clojure

Published at
11/2/2020
Categories
clojure
tree
algorithms
clojurescript
Author
ertugrulcetin
Author
13 person written this
ertugrulcetin
open
Using Specter on tree data structures in Clojure

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))
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode

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)))))
Enter fullscreen mode Exit fullscreen mode

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))))
Enter fullscreen mode Exit fullscreen mode

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)))
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode

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?)))
Enter fullscreen mode Exit fullscreen mode

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)))
Enter fullscreen mode Exit fullscreen mode

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.

clojurescript Article's
30 articles in total
Favicon
Querido Yo del Futuro: Hoy intentaremos configurar una aplicación fullstack en Clojure
Favicon
Why I chose Clojure/Script for building Vade Studio
Favicon
Converting JS Libraries to Clojure: Part 1
Favicon
Deploy your ClojureScript App to Cloudflare Workers
Favicon
shadow-cljs and running tests
Favicon
Giving new life to existing Om legacy SPAs with re-om
Favicon
Is Clojure the only language you need?
Favicon
Building an Application with ClojureScript
Favicon
How to Set up A Clojure Script and Phoenix Project
Favicon
How to create a library that works with Clojure and ClojureScript
Favicon
Setup shadow-cljs react project
Favicon
Logging readable ClojureScript (.cljs) errors to sentry!!
Favicon
How can I create a ClojureScript web app from scratch with Reagent and npm?
Favicon
Set up SSL/TLS for shadow-cljs https server
Favicon
ClojureScript on Cloudflare Workers
Favicon
Storybook.JS with Shadow-CLJS
Favicon
World Statistics Exercise
Favicon
The Pleasure of Clojure(Script): Part 1
Favicon
Using Specter on tree data structures in Clojure
Favicon
Clojure Re-Frame Exercise
Favicon
¿Por qué Clojure?
Favicon
Implementing the feed
Favicon
Try something new this week
Favicon
ClojureScript async MVU
Favicon
ClojureScript simple MVU loop
Favicon
Integrating ClojureScript with JavaScript tooling
Favicon
Understanding Transducers in JavaScript
Favicon
Casting visual spells with p5.js and ClojureScript, part 1
Favicon
ClojureScript REPL Workflow
Favicon
Developing, Testing and Deploying AWS Lambda Functions written in ClojureScript

Featured ones: