How can I get the nested keys of a map in clojure?

Question

if my structure is

{ :a :A
  :b :B
  :c {
       :d :D
     }
  :e {
       :f {
            :g :G
            :h :H
          }
     }
}

I would like to get a function called keys-in that returns something like:

[[:a] [:b] [:c :d] [:e :f :g] [:e :f :h]]

so then I can do something like:

(not-any? nil? (map #(get-in my-other-map %1) (keys-in my-map)))

So I can be sure that my-other-map has the same keys that my-map

Answer 1

(defn keys-in [m]
  (if (map? m)
    (vec 
     (mapcat (fn [[k v]]
               (let [sub (keys-in v)
                     nested (map #(into [k] %) (filter (comp not empty?) sub))]
                 (if (seq nested)
                   nested
                   [[k]])))
             m))
    []))

;; tests
user=> (keys-in nil)
[]
user=> (keys-in {})
[]
user=> (keys-in {:a 1 :b 2}))
[[:a] [:b]]
user=> (keys-in {:a {:b {:c 1}}})
[[:a :b :c]]
user=> (keys-in {:a {:b {:c 1}} :d {:e {:f 2}}})
[[:a :b :c] [:d :e :f]]

Answer 2

(defn keys-in [m]
  (if (or (not (map? m))
          (empty? m))
    '(())
    (for [[k v] m
          subkey (keys-in v)]
      (cons k subkey))))

Answer 3

If you don't need a lazy result and just want to be fast, try using reduce-kv.

(defn keypaths
  ([m] (keypaths [] m ()))
  ([prev m result]
   (reduce-kv (fn [res k v] (if (map? v)
                              (keypaths (conj prev k) v res)
                              (conj res (conj prev k))))
              result
              m)))

If you also want to support vector indices (as with get-in or update-in), test with associative? instead of map?. If you want intermediate paths, you can conj those on too. Here's a variant:

(defn kvpaths-all2
  ([m] (kvpaths-all2 [] m ()))
  ([prev m result]
   (reduce-kv (fn [res k v] (if (associative? v)
                              (let [kp (conj prev k)]
                                (kvpaths-all2 kp v (conj res kp)))
                              (conj res (conj prev k))))
              result
              m)))

Answer 4

Obligatory zippers version

(require '[clojure.zip :as z])

(defn keys-in [m] 
  (letfn [(branch? [[path m]] (map? m)) 
          (children [[path m]] (for [[k v] m] [(conj path k) v]))] 
    (if (empty? m) 
      []
      (loop [t (z/zipper branch? children nil [[] m]), paths []] 
        (cond (z/end? t) paths 
              (z/branch? t) (recur (z/next t), paths) 
              :leaf (recur (z/next t), (conj paths (first (z/node t)))))))))