Quick Containment in a Arbitrary Depth Map

contains? will check (in the case of a map) for a key within a map. (contains? data v) returns true when v is :a or :f. (contains? data :c) will return false as :c is not a top level key in data.

Problem

I want to ask "containment" questions about the keys at ALL levels within a map. I want to be able to determine not just that :a and :f are within the map but also that :b, :c, :d, :e, and :g are "contained" as well. Conversely, I want to know that :z is not a key within any map in data.

Solution

(defn- add-children-metadata [m]
  (->> m
       vals
       (map (comp :all-keys meta))
       (apply clojure.set/union (-> m keys set))
       (assoc (meta m) :all-keys)
       (with-meta m)))

(defn map->containment-map
  "Sets :all-keys metadata for every map in m; :all-keys holds every key in this map and for all submaps"
  [m]
  (-> (fn [acc k v]
        (assoc acc k (if (map? v)
                       (-> v map->containment-map add-children-metadata)
                       v)))
      (reduce-kv {} m)
      add-children-metadata))

Usage

(def data {:a {:b nil 
               :c {:d nil 
                   :e {}}}
           :f {:g nil}})
           
(def contained-data (map->containment-map data))

Note that data and contained-data are equal.

(= data contained-data)

The difference is that contained-data has the :all-keys key within its metadata.

(-> contained-data meta :all-keys)

Examples

With this metadata, you can ask containment questions about keys at all levels. Each submap within contained-data also contains :all-keys in their metadata.

contained-data contains the key :f

(-> contained-data meta :all-keys (contains? :f) (= true))

contained-data does not contain the key :x

(-> contained-data meta :all-keys (contains? :x) (= false))

Key :a under contained-data has keys :b :c :d and :e

(-> contained-data :a meta :all-keys (= #{:b :c :d :e}))

Conclusion

That's it. You can use the :all-keys metadata to either:

1. Do fast containment lookup of all keys within a map.
2. Get a sequence of all (unique) keys within a map.