Clojure function definition: tree from paths

Question

I'd like to define a function f that returns a tree (as nested maps) given a sequence of paths through that tree.

e.g.,

(def paths [[:a :b :c]
            [:a :b :d]
            [:b :d]
            [:b :e]
            [:b :e :a]])
(f paths) =>
[[:a [:b
       :c :d]]
 [:b :d
    [:e :a]]]

Assume that all vectors indicate paths stemming from the same root.

How might this function be defined functionally in a single pass?

I'm interested in behavior opposite to the function referenced here.

Answer 1

I would do it with maps like so:

(def paths [[:a :b :c]
            [:a :b :d]
            [:b :d]
            [:b :e]
            [:b :e :a]])

(defn update-with-path
  [tree-map path-vec]
  (assoc-in tree-map path-vec nil) )

(defn build-tree [paths]
  (reduce
    update-with-path
    {} paths )
  )

(deftest t-global
  (is= {:a nil} (update-with-path {} [:a]))
  (is= {:a {:b nil}} (update-with-path {} [:a :b]))
  (is= {:a {:b {:c nil}}} (update-with-path {} [:a :b :c]))

  (is= (build-tree paths)
    { :a
      { :b
        { :c nil
          :d nil}}
      :b
      {
        :d nil
        :e
          { :a nil }}}
    )
  )

Using maps is easy with assoc-in. All leaf values have nil as their value, while non-leaf values have a map as their value. Also, using a nested map structure means we don't have to worry about duplicates.

You can find all of the leaf nodes like so:

(ns xyz...
 (:require
    [tupelo.core :as t]  ))
(t/refer-tupelo)

(def t1 (build-tree paths))
(def cum (atom []))
(defn walker [path tree]
  (if (nil? tree)
    (swap! cum t/append path)
    (doseq [key (keys tree)]
      (walker (t/append path key) (t/grab key tree)))))
(walker [] t1)
(spyx @cum)

 => [[:a :b :c] [:a :b :d] [:b :d] [:b :e :a]]

Then modify the tree creation code do make a new tree with vector leaves:

(defn update-with-path-2
  [tree-map path-vec]
  (assoc-in tree-map path-vec path-vec))

(defn build-tree-2 [paths]
  (reduce
    update-with-path-2
    {} paths)
  )
(spyx (build-tree-2 @cum))

 => {:a {:b {:c [:a :b :c], 
             :d [:a :b :d]}}, 
     :b {:d [:b :d], 
         :e {:a [:b :e :a]}}}

This code uses the Tupelo library.