Clojure: Remove value in all leaves of a tree

I implemented a trie in clojure but I'm struggling with a remove-values function. The structure I use looks like this:

(def trie {\a {:value #{"val1" "val2"}}
           \b {\c     {:value #{"val1"}}
               :value #{"val2"}}})

I want to call a function like this (remove-value trie "val1") and get a structure where all instances of "val1" are removed from the sets in the leave nodes. The resulting trie would look like this:

{\a {:value #{"val2"}}
 \b {\c     {:value #{}}
     :value #{"val2"}}}

Or better yet:

{\a {:value #{"val2"}}
 \b {:value #{"val2"}}}

From what I've seen here on SO this could probably be done in five lines of clojure but I can't figure out how. Also I'm not married to the data structure, if you need to alter it for an idiomatic version to work, feel free, as long as it's still a trie.

Solution

I would suggest to use very regular structure of trie: A map whose first entry is always :value with a #{} of value. All other keys are children which contain as values themselvers tries. (Meaning they have a :value key at the beginning!)

Then define car/first, cdr/rest, cons, map for hash-maps (-map).

(defn first-map [m]
  (let [k (first (keys m))]
     {k (k m)}))

(defn rest-map [m]
  (into {} (map (fn [k] {k (k m)}) (rest (keys m)))))

(defn cons-map [m1 m2]
  (into {} (concat m1 m2)))

(defn map-map [f m & args]
  (into {} (map (fn [k] {k (apply f (k m) args)}) 
                (keys m))))

Try them out:

(def m {:a 1 :b 2 :c 3})

(first-map m)                 ;; => {:a 1}
(rest-map m)                  ;; => {:b 2 :c 3}
(cons-map {:a 1} {:b 2 :c 3}) ;; => {:a 1 :b 2 :c 3}
(map-map #(+ % 1) m)          ;; => {:a 2, :b 3, :c 4}
(map-map #(+ %1 %2) m 1)      ;; => {:a 2, :b 3, :c 4}

Then, using them define remove-value

(defn remove-value [trie val]
  (cons-map {:value (disj (:value (first-map trie)) val)}
            (map-map remove-value (rest-map trie) val)))

Originally, I wrote:

(defn remove-value [trie val]
  (cond (empty? (rest-map trie))
        {:value (disj (:value (first-map trie)) val)}
        :else (cons-map {:value (disj (:value (first-map trie)) val)}
                        (map-map remove-value (rest-map trie) val))))

But then realized that the :else branch alone does this automatically since map-map on an empty (rest-map trie) results in just {:value (disj (:value (first-map trie)) val)} - which can be alternatively expressed also as (let [[k v] (first-map trie)] {k (disj v val)}).

Your trie would be:

(def trie {:value #{}
           :a {:value #{"val1" "val2"}}
           :b {:value #{"val2"}
               :c {:value #{"val1"}}}})

Note: a tree in toplevel will always begin with :value #{} (the root of the tree). :value's value will be always a set either empty #{} or with one or multiple elements in it. So, every child is a complete trie in itself.

user=> (remove-value trie "val1")
{:value #{}, :a {:value #{"val2"}}, :b {:value #{"val2"}, :c {:value #{}}}}
user=> (remove-value trie "val2")
{:value #{}, :a {:value #{"val1"}}, :b {:value #{}, :c {:value #{"val1"}}}}