Iteratively Construct Trie from a Tree

Question

Introduction

The following function iteratively traverses a tree structure made of nested vectors. It tests each leaf against a predicate. The paths to all leaves which pass that truth-test are returned in a Trie structure. The later describes all found paths in a non-redundant way.

(defn get-trie-of-matches [is? tree]
  (loop [[tree i path fk] [tree 0 [] nil]
         accum {}]
    (cond
      (>= i (count tree)) ;; end of level / go up
      (if (nil? fk) accum (recur fk accum))

      (vector? (tree i)) ;; level down
      (recur [(tree i) 0 (conj path i) [tree (inc i) path fk]] accum)

      (is? (tree i)) ;; match
      (let [new-accum (assoc-in accum (conj path i) {})]
        (recur [tree (inc i) path fk] new-accum))

      :else ;; next on same level
      (recur [tree (inc i) path fk] accum))))

For further explanations see this post.

Example

Consider the following tree

(def tree [7 9 [7 5 3 [4 6 9] 9 3] 1 [2 7 9 9]])

Applied to the function, using even? as a predicate:

(get-trie-of-matches even? tree)
=> {2 {3 {0 {}, 1 {}}}, 4 {0 {}}}

The result describes the three paths to even numbers in tree. Namely 2-3-0, 2-3-1 and 4-0.

Problem

Even though the above function works, there might be better ways to construct the Trie while traversing the tree. At the moment a hash-map is flooded. On each match via assoc-in. The algorithm traverses the tree structure relatively from level to level but attaches each path in a global fashion to accum, which is not necessary. Also this method is only possible since a hashmap is used. It might anyways be better to use a sequential data-structure for the Trie in order to facilitate further iterations over it. This could not be adopted to the above method.

Question

How could a Trie be created from within the above function get-trie-of-matches without relying on hash-map specific 'global' 'write' functions?

Answer 1

I would propose to take a look at clojure's walk api.

It allows you to recursively apply some function to nested collections. In this case you could use postwalk:

user> (require '[clojure.walk :as w])
user> (w/postwalk-demo [1 3 [4 [6] 7] [[8]]])
Walked: 1
Walked: 3
Walked: 4
Walked: 6
Walked: [6]
Walked: 7
Walked: [4 [6] 7]
Walked: 8
Walked: [8]
Walked: [[8]]
Walked: [1 3 [4 [6] 7] [[8]]]

[1 3 [4 [6] 7] [[8]]]

The key thing is you can replace any item at every step:

user> (w/postwalk #(if (coll? %) (reverse %) (inc %))
                  [1 3 [4 [6] 7] [[8]]])

(((9)) (8 (7) 5) 4 2)

Here we increment all the numbers, and reverse all the collections, keeping the nested structure.

Now applying to your task: You could walk through your tree, keeping just even number's indices and not empty collections (e.g. collections containing even numbers, and not empty collections):

;; helper function
(defn empty-coll? [item]
  (and (coll? item) (not (seq item))))

(defn make-trie [pred tree]
  (w/postwalk
   #(if (coll? %)
      (keep-indexed (fn [idx item]
                      (cond (empty-coll? item) nil
                            (coll? item) (list idx item)
                            item idx
                            :else nil))
                    %)
      (pred %))
   tree))

in repl:

user> (def tree [7 9 [7 5 3 [4 6 9] 9 3] 1 [2 7 9 9]])
#'user/tree

user> (make-trie even? tree)
((2 ((3 (0 1)))) (4 (0)))

user> (make-trie #(> % 7) tree)
(1 (2 ((3 (2)) 4)) (4 (2 3)))

The structure is similar to your map. In fact you can produce any structure you want with minor changes to the function, for example your map structure:

(defn make-trie-map [pred tree]
  (w/postwalk
   #(if (coll? %)
      (into {}
            (keep-indexed (fn [idx item]
                            (cond (empty-coll? item) nil
                                  (coll? item) {idx item}
                                  item {idx {}}
                                  :else nil))
                          %))
      (pred %))
   tree))

user> (make-trie-map even? tree)
{2 {3 {0 {}, 1 {}}}, 4 {0 {}}}