# How to transform nested map into flat sequence of \[path, value\] pairs
**URL:** https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801
**Category:** How to?
**Created:** [April 4, 2022, 4:58pm UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801 "2022-04-04T16:58:55Z")
**Posts on this page:** 20
**Page:** 1
### Author:  [@teodorlu](https://clojureverse.org/u/teodorlu)
#### Post date: [April 4, 2022, 4:58pm UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/1 "2022-04-04T16:58:56Z")
Hi!
Some conversation on the Clojurians Slack got me curious about _normalizing_ maps into a vector of [path value] pairs.
```clojure
(defn todo [m])
;; such that
(= (todo
{:a 99
:x {:b 999
:y {:z 123
:w 456}}})
[[:a] 99
[:x :b] 999
[:x :y :z] 123
[:x :y :w] 456])
```
How would you write `todo`?
* * *
On the Clojurians Slack, this started in a [thread](https://clojurians.slack.com/archives/CJ322KHNX/p1649027696146939?thread_ts=1648657000.940199&cid=CJ322KHNX), then I asked a [separate question](https://clojurians.slack.com/archives/C053AK3F9/p1649090531582539).
Teodor
---
### Author:  [@joinr](https://clojureverse.org/u/joinr)
#### Post date: [April 4, 2022, 5:30pm UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/2 "2022-04-04T17:30:36Z")
I resorted to dumb recursion:
```auto
ed. recovery implementation was incorrect per sample output, now is correct.
```
```auto
(defn recover [xs]
(reduce (fn [acc x]
(if (or (vector? x) (not (seq x)))
(into acc x)
(into acc (recover x))))
[] xs))
(defn normalize
([path m]
(if (map? m)
(for [[k v] m]
(normalize (conj path k) v))
[path m]))
([m] (-> (normalize [] m)
recover)))
(def m {:a 99, :x {:b 999, :y {:z 123, :w 456}}})
;;user=> (normalize m)
;;[[:a] 99 [:x :b] 999 [:x :y :z] 123 [:x :y :w] 456]
```
seems like this is probably abstract-able into some kind of general reducible path walk thing.
---
### Author:  [@zcaudate](https://clojureverse.org/u/zcaudate)
#### Post date: [April 5, 2022, 3:29am UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/3 "2022-04-05T03:29:56Z")
where’s the faster, asynchronous (and obviously more superior) transducer implementation?
---
### Author:  [@teodorlu](https://clojureverse.org/u/teodorlu)
#### Post date: [April 5, 2022, 6:08am UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/4 "2022-04-05T06:08:51Z")
@zcaudate I would love to see you give it a shot 😊
Bonus points if arbitrary deep maps don’t blow up the stack.
---
### Author:  [@joinr](https://clojureverse.org/u/joinr)
#### Post date: [April 5, 2022, 6:28am UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/5 "2022-04-05T06:28:12Z")
next to your humility, tool.
---
### Author:  [@zcaudate](https://clojureverse.org/u/zcaudate)
#### Post date: [April 5, 2022, 7:04am UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/6 "2022-04-05T07:04:59Z")
> [@teodorlu](#):
>
> Bonus points if arbitrary deep maps don’t blow up the stack.
Have you tried already? Awesome. How deep do the maps have to get to blow up?
I’m not feeling masochistic enough to try but here’s a reduce implementation that may come in handy.
>
---
### Author:  [@zcaudate](https://clojureverse.org/u/zcaudate)
#### Post date: [April 5, 2022, 7:07am UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/7 "2022-04-05T07:07:45Z")
here’s a js version that’s faster:
```auto
function nested_keys(m,path){
let out = [];
for(let [k,v] of Object.entries(m)){
if((null != v) && ("object" == (typeof v)) && !Array.isArray(v)){
for(let e of nested_keys(v,[...path,k])){
out.push(e);
};
}
else{
out.push([[...path,k],v]);
}
};
return out;
}
nested_keys({"a":{"b":{"c":1,"d":2},"e":{"f":4,"g":5}}},[]);
=> [[["a", "b", "c"], 1]
[["a", "b", "d"], 2]
[["a", "e", "f"], 4]
[["a", "e", "g"], 5]]
```
---
### Author:  [@joinr](https://clojureverse.org/u/joinr)
#### Post date: [April 5, 2022, 8:27am UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/8 "2022-04-05T08:27:07Z")
I didn’t catch the arbitrary nesting requirement. I think 0 seqs, with the ability to handle arbitrary nesting (I also think the docstring for clj jvm iterate is outdated, as it returns an internally reducible object that can optionally be seq coerced) [happy to be shown otherwise]:
```auto
(require '[net.cgrand.xforms :as x])
(defn compute-paths [{:keys [paths]}]
(->> (x/for [[p c] paths]
(if (map? c)
(eduction cat
(x/for [[chld xs] c]
[(conj p chld) xs]))
[p c]))
(eduction cat (partition-all 2))))
(defn update-paths [{:keys [acc paths]} new-paths]
(let [{:keys [mods adds]}
(group-by (fn [[_ v]]
(if (map? v) :mods :adds)) new-paths)
res {:acc (into acc adds)
:paths mods}]
(if (empty? mods)
(reduced res)
res)))
;;swap (into [] (comp x/last (map :acc) cat cat)))) to eduction.
(defn normalize [m]
(->> {:acc [] :paths (into {} (map (fn [[k v]] [[k] v])) m)}
(iterate (fn [seed]
(->> seed
compute-paths
(update-paths seed))))
(eduction x/last (map :acc) cat cat)
(into [])))
;;user=> (normalize m)
;;[[:a] 99 [:x :b] 999 [:x :y :z] 123 [:x :y :w] 456]
```
---
### Author:  [@joinr](https://clojureverse.org/u/joinr)
#### Post date: [April 5, 2022, 2:20pm UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/9 "2022-04-05T14:20:03Z")
shorter, faster recursive impl with mutation (unsafe results), possible blown stack.
```auto
(require '[net.cgrand.xforms :as x])
(import '[java.util List ArrayList])
(defn normalize [m]
(let [aux (fn normalize! [^List acc ^List p m]
(if (map? m)
(->> (x/for [[k v] m]
(normalize! acc (doto p (.add k)) v))
(reduce (fn [_ _] acc)))
(doto acc (.add (.clone p)) (.add m))))]
(aux (ArrayList.) (ArrayList.) m)))
```
---
### Author:  [@joinr](https://clojureverse.org/u/joinr)
#### Post date: [April 5, 2022, 4:32pm UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/10 "2022-04-05T16:32:41Z")
I think this one will leverage some parallelism (although retaining order) while allowing arbitrary nesting depth. An unordered variant (pipeline preserves order) would get more gainz. Could be a fold variant around here somewhere.
```auto
(require '[net.cgrand.xforms :as x])
(require '[clojure.core.async :as a])
(defn normalize [m]
(let [out (a/chan 10)
pending (a/chan 10)
remaining (atom 0)
push-work! (fn [n xs]
(do (swap! remaining + n)
(a/onto-chan! pending xs false)))
_ (push-work! (count m) (x/for [[k v] m] [[k] v]))
walk (fn [[p xs]]
(let [res (if (map? xs)
(do (push-work! (count xs)
(x/for [[k v] xs]
[(conj p k) v]))
:ignore)
[p xs])
_ (when (zero? (swap! remaining dec))
(a/close! pending))]
res))]
(a/pipeline-blocking
(+ 2 (.availableProcessors (Runtime/getRuntime)))
out
(comp (map walk)
(filter #(not= % :ignore))
cat)
pending)
(->> out
(a/into [])
a/
### Author:  [@teodorlu](https://clojureverse.org/u/teodorlu)
#### Post date: [April 5, 2022, 10:05pm UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/11 "2022-04-05T22:05:31Z")
Using core.async internally for this is really interesting - I would never have thought of that.
---
### Author:  [@joinr](https://clojureverse.org/u/joinr)
#### Post date: [April 6, 2022, 2:18am UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/12 "2022-04-06T02:18:45Z")
Fun toy problem. 🖖
---
### Author:  [@zcaudate](https://clojureverse.org/u/zcaudate)
#### Post date: [April 7, 2022, 2:46am UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/13 "2022-04-07T02:46:23Z")
@joinr, it’s really interesting what you’ve done.
I’ll put what I’ve extracted out from your example as a pseudo lisp targeting js (hopefully it’s pretty readable). Because JS is single threaded, I’m using a standard array for accumulation but on the JVM, either an atom or a concurrent deque would work.
* * *
The most important bit is the step function for `nested-keys-step-fn`.
It takes three arguments → `args`, `queue` and accumulated `output`
It linearises a nested loop by taking an entry from a queue, doing an operation and putting more tasks on the queue if a child is an object:
```clojure
(defn.js nested-keys-step-fn
[args queue out]
(var [path m] args)
(k/for:object [[k v] m]
(cond (k/obj? v)
;; add to queue if object
(x:arr-push queue [[(:.. path) k] v])
:else
;; add to accumulated output otherwise
(x:arr-push out [[(:.. path) k] v])))
(return [queue out]))
```
Examples:
```clojure
(walk-step-fn [[] {"a" {"b" 2 "c" 3}}]
[]
[])
=> [[[["a"] {"b" 2, "c" 3}]] ;; queue
[]] ;; output
(walk-step-fn [["a"] {"b" 2, "c" 3}]
[]
[])
=> [[] ;; queue
[[["a" "b"] 2] [["a" "c"] 3]]] ;;output
```
* * *
Because the step function turns a nested loop into a linear one, we can use a generic `walk` implementation (using iterators, transducers, parallell threads, whatever).
The simplest is a while loop:
```clojure
(defn.js walk [step-fn queue]
(var out [])
(while (< 0 (k/len queue))
(var args (x:arr-pop queue))
(step-fn args queue out))
(return out))
```
and nested keys can be defined in terms of the walk function:
```clojure
(defn.js nested-keys
[m]
(return (-/walk -/walk-step-fn [[[] m]])))
(nested-keys {:a {:b 1 :c 2}
:d {:e 1 :f 2}})
=> [[["d" "e"] 1]
[["d" "f"] 2]
[["a" "b"] 1]
[["a" "c"] 2]]
```
The simplest async version of walk on JS looks like this:
```clojure
(defn.js walk-async [step-fn queue out]
(return (j/future
(var args (x:arr-pop queue))
(step-fn args queue out)
(if (< 0 (k/len queue))
(return (-/walk-async step-fn queue out))
(return out)))))
(defn.js nested-keys-async
[m]
(return (-/walk-async -/walk-step-fn [[[] m]] [])))
```
and output:
```clojure
(j/
### Author:  [@zcaudate](https://clojureverse.org/u/zcaudate)
#### Post date: [April 7, 2022, 2:46am UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/14 "2022-04-07T02:46:52Z")
The runnable javascript is here:
```javascript
function walk_step_fn(args,queue,out){
let [path,m] = args;
for(let [k,v] of Object.entries(m)){
if((null != v) && ("object" == (typeof v)) && !Array.isArray(v)){
queue.push([[...path,k],v]);
}
else{
out.push([[...path,k],v]);
}
};
return [queue,out];
}
function walk(step_fn,queue){
let out = [];
while(0 < (queue).length){
let args = queue.pop();
step_fn(args,queue,out);
}
return out;
}
function walk_async(step_fn,queue,out){
return new Promise(function (resolve,reject){
try{
resolve( (function (){
let args = queue.pop();
step_fn(args,queue,out);
if(0 < (queue).length){
return walk_async(step_fn,queue,out);
}
else{
return out;
}
})());
}
catch(e){
reject(e);
}
});
}
function nested_keys(m){
return walk(walk_step_fn,[[[],m]]);
}
function nested_keys_async(m){
return walk_async(walk_step_fn,[[[],m]],[]);
}
```
---
### Author:  [@kennytilton](https://clojureverse.org/u/kennytilton)
#### Post date: [April 10, 2022, 10:20pm UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/15 "2022-04-10T22:20:52Z")
What part of “tree” do you not respect? Resistance is futile! 🙂
---
### Author:  [@Josh\_Lemer](https://clojureverse.org/u/Josh_Lemer)
#### Post date: [April 14, 2022, 5:30am UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/16 "2022-04-14T05:30:58Z")
a simple and stack-safe solution
```clojure
(defn todo [m]
(let [out (transient [])]
(loop [path []
stack (list m)]
(if (not-empty stack)
(let [[x & xs] stack]
(if (empty? x)
(if (not-empty path)
(recur (pop path) xs))
(let [[k v] (first x)
kvs (rest x)
next-path (conj path k)]
(if (map? v)
(do
(recur next-path (conj xs kvs v)))
(do
(conj! out [next-path v])
(recur path (conj xs kvs)))))))))
(persistent! out)))
```
---
### Author:  [@joinr](https://clojureverse.org/u/joinr)
#### Post date: [April 14, 2022, 7:34am UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/17 "2022-04-14T07:34:09Z")
I think (in general) you need to put the `out` transient into an atom and `swap!` via `conj!` to mutate it (and capture the result), or include it in the loop bindings and explicitly pass the result of `conj!` to maintain a reference to the returned result. Depending on undefined behaviors, if you treat it as a “bash in place” mutable container and apply updates via a side-effecting model without capturing the result of `conj!` (as in the current `do` form), you can end up with incorrect data since the original reference may be modified under the hood (the result of `conj!` - the current state of the transient - may be a different object than the original bound value - which is not reflected in the binding). I had this error affect me years ago; uncertain what the exact failure semantics are, but the [docs](https://clojure.org/reference/transients#_how_they_work) deter the bash-in-place pattern: “Note in particular that transients are not designed to be bashed in-place. You must capture and use the return value in the next call. In this way, they support the same code structure as the functional persistent code they replace.”
[incorrect example reference](https://clojuredocs.org/clojure.core/conj%21#example-5e0d14f7e4b0ca44402ef804)
---
### Author:  [@teodorlu](https://clojureverse.org/u/teodorlu)
#### Post date: [April 14, 2022, 8:31am UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/18 "2022-04-14T08:31:16Z")
Ah, so each time you conj! onto a mutable container, you get the “new” container back (but the last one can’t be used), and have to use that?
Thanks for explaining.
Shouldn’t this be possible to fix in @Josh_Lemer’s answer by adding the transient as a loop/recur argument?
---
### Author:  [@joinr](https://clojureverse.org/u/joinr)
#### Post date: [April 14, 2022, 1:22pm UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/19 "2022-04-14T13:22:51Z")
> Shouldn’t this be possible to fix in @Josh_Lemer’s answer by adding the transient as a loop/recur argument?
Yes, that was an alternative in the original suggestion.
Using `swap!` and an atom probably requires slightly less transformation of the original solution though.
---
### Author:  [@Josh\_Lemer](https://clojureverse.org/u/Josh_Lemer)
#### Post date: [April 14, 2022, 2:49pm UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/20 "2022-04-14T14:49:13Z")
Sorry I always forget about that!
```clojure
(defn todo [m]
(loop [path []
stack (list m)
out (transient [])]
(if (not-empty stack)
(let [[x & xs] stack]
(if (empty? x)
(if (empty? path)
(persistent! out)
(recur (pop path) xs out))
(let [[[k v] & kvs] x
next-path (conj path k)]
(if (map? v)
(recur next-path (conj xs kvs v) out)
(recur path (conj xs kvs) (conj! out [next-path v])))))))))
```
[Next page](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801.md?page=2)