# 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:** 11
**Page:** 2

<div class="post-metadata">

### Author: ![Josh\_Lemer](https://clojureverse.org/user_avatar/clojureverse.org/josh_lemer/32/2308_2.png) [@Josh\_Lemer](https://clojureverse.org/u/Josh_Lemer)
#### Post date: [April 14, 2022, 2:55pm UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/21 "2022-04-14T14:55:54Z")

</div>

And a stack-safe, lazy implementation using generators from Cloroutine ([cloroutine/01-generators.md at master · leonoel/cloroutine · GitHub](https://github.com/leonoel/cloroutine/blob/master/doc/01-generators.md))!

```clojure
(defn todo [m]
  (generator
   (loop [path []
          stack (list m)]
     (if (not-empty stack)
       (let [[x & xs] stack]
         (if (empty? x)
           (if (empty? path)
             (recur (pop path) xs))
           (let [[[k v] & kvs] x
                 next-path (conj path k)]
             (if (map? v)
               (recur next-path (conj xs kvs v))
               (do
                 (yield [next-path v])
                 (recur path (conj xs kvs)))))))))))

```

I really love this, this is a great example of how generators can really come in handy and express an algorithm much more cleanly than in other ways. Why aren’t we all using these already??

---

<div class="post-metadata">

### Author: ![joinr](https://clojureverse.org/user_avatar/clojureverse.org/joinr/32/1861_2.png) [@joinr](https://clojureverse.org/u/joinr)
#### Post date: [April 14, 2022, 4:52pm UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/22 "2022-04-14T16:52:43Z")

</div>

> [@Josh\_Lemer](#):
>
> Why aren’t we all using these already??

I really like these (originally used them in F# quite a bit to define sequences and even computation expressions (monads), as well as python stuff). Curious what the limitations there are - in the naive implementation for `generator`, there is at least a consistent dynamic var deref that has to occur (that could likely be optimized out though, I think this is for demonstrative purposes). So naive performance appears impacted, likely only in this implementation:

```auto
(defn my-repeat [x]
  (generator
   (loop []
     (yield x)
     (recur))))

cloro.core> (time (dotimes [i 1] (last (take 1000000 (my-repeat :a)))))
"Elapsed time: 681.395 msecs"
nil

;;naive pure lazy seq
(defn repeat-l [x]
  (lazy-seq
   (cons x (repeat-l x))))

cloro.core> (time (dotimes [i 1] (last (take 1000000 (repeat-l :a)))))
"Elapsed time: 156.2908 msecs"

cloro.core> (time (dotimes [i 1] (last (take 1000000 (repeat :a)))))
"Elapsed time: 89.4764 msecs"
nil

```

I assume one value prospect would be consistent costs with lazy sequences, while allowing imperative definition of the sequence, or even better performance (e.g. defining a generator that returns something iterable/reducible that can provide an efficient baseline for other stuff like transduce). Definitely a cool tool (I need some time to [go through implementation though](https://github.com/leonoel/cloroutine/blob/master/src/cloroutine/impl.cljc#L95), hah).

---

<div class="post-metadata">

### Author: ![lilactown](https://clojureverse.org/user_avatar/clojureverse.org/lilactown/32/1221_2.png) [@lilactown](https://clojureverse.org/u/lilactown)
#### Post date: [April 14, 2022, 7:01pm UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/23 "2022-04-14T19:01:58Z")

</div>

I decided to take a crack at this.

My first intuition was that this seems like a map over each entry in a map, where if the child is a map it will recurse. So i started naively with

```clojure
(defn todo
  ([path m]
  (map
   (fn [[key x]]
     (if (map? x)
       (todo (conj path key) x)
       [(conj path key) x]))
   m))
  ([m] (todo [] m)))

```

this doesn’t quite work how the initial question asked though

```clojure
user=> (todo {:a 99
              :x {:b 999
                  :y {:z 123
                      :w 456}}})
([[:a] 99] ([[:x :b] 999] ([[:x :y :z] 123] [[:x :y :w] 456])))

```

Changing to `mapcat` solved this.

Once I had identified how to do this using core sequence operations, I then used [cascade](https://github.com/lilactown/cascade) to make it eager and stackless via continuation passing

```clojure
(require '[cascade.core :as c])

(defn todo-k
  ([k path m]
   (c/mapcat
    k
    (fn [k [key x]]
      (if (map? x)
        (todo-k k (conj path key) x)
        #(k [(conj path key) x])))
    m))
  ([m]
   (trampoline (todo-k identity [] m))))

(todo-k {:a 99
         :x {:b 999
             :y {:z 123
                 :w 456}}})
;; => ([:a] 99 [:x :b] 999 [:x :y :z] 123 [:x :y :w] 456)

```

---

<div class="post-metadata">

### Author: ![lilactown](https://clojureverse.org/user_avatar/clojureverse.org/lilactown/32/1221_2.png) [@lilactown](https://clojureverse.org/u/lilactown)
#### Post date: [April 14, 2022, 7:09pm UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/24 "2022-04-14T19:09:06Z")

</div>

you could make this async by using a special `trampoline` that understood how to await an async value and then used some async framework to fork or defer the computation when calling `k`.

---

<div class="post-metadata">

### Author: ![leonoel](https://clojureverse.org/user_avatar/clojureverse.org/leonoel/32/3915_2.png) [@leonoel](https://clojureverse.org/u/leonoel)
#### Post date: [April 16, 2022, 7:52pm UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/25 "2022-04-16T19:52:31Z")

</div>

> [@joinr](#):
>
> Curious what the limitations there are - in the naive implementation for `generator`, there is at least a consistent dynamic var deref that has to occur (that could likely be optimized out though, I think this is for demonstrative purposes).

I’ve made [additional measurements](https://gist.github.com/leonoel/7e6cb47399f6fc7d387e393e2d7de74a). The results confirm your insight, the performance hit is largely due to the dynamic var access. `java.lang.ThreadLocal` is much faster.

---

<div class="post-metadata">

### Author: ![Josh\_Lemer](https://clojureverse.org/user_avatar/clojureverse.org/josh_lemer/32/2308_2.png) [@Josh\_Lemer](https://clojureverse.org/u/Josh_Lemer)
#### Post date: [April 16, 2022, 9:22pm UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/26 "2022-04-16T21:22:49Z")

</div>

I also have created an implementation which eliminates almost all overhead of using the coroutines library [gen.clj · GitHub](https://gist.github.com/joshlemer/8305c8447cd98d1c01faa69b9b5077f0)

---

<div class="post-metadata">

### Author: ![didibus](https://clojureverse.org/user_avatar/clojureverse.org/didibus/32/951_2.png) [@didibus](https://clojureverse.org/u/didibus)
#### Post date: [April 16, 2022, 10:53pm UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/27 "2022-04-16T22:53:34Z")

</div>

All these “generator/coroutine” solution people are bringing up, may I ask what’s the point of them? Just so you can implement a recursive solution that doesn’t consume stack?

---

<div class="post-metadata">

### Author: ![Josh\_Lemer](https://clojureverse.org/user_avatar/clojureverse.org/josh_lemer/32/2308_2.png) [@Josh\_Lemer](https://clojureverse.org/u/Josh_Lemer)
#### Post date: [April 16, 2022, 11:29pm UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/28 "2022-04-16T23:29:27Z")

</div>

Do you mean, what is the point of using generators at all? I think the Motivation section of the Python Generators PEP articulates it quite well [PEP 255 – Simple Generators | peps.python.org](https://peps.python.org/pep-0255/#motivation)

To paraphrase, the point is that as the complexity of a lazy “data producer-like thing” (iterator/sequence/whatever) increases, it becomes more and more difficult to manage its state by hand. Every time a `.next()` is called, the producer has to read from manually encoded state, continue processing to the next element, and ensure the state is stored correctly for the next `.next()` call. This is much more difficult to do in a correct and performant way than it is to use the language’s built in control structures, scoped variables, etc to manage its state.

This pushes developers to make a choice between giving up and producing the data strictly all at once in memory, and doing the much more difficult and error-prone task of manually constructing a lazy data producer.

This is where generators save us because they allow us to lazily produce data, while enjoying the benefits of all the language’s natural control structures. We get to have our cake and eat it too.

---

<div class="post-metadata">

### Author: ![didibus](https://clojureverse.org/user_avatar/clojureverse.org/didibus/32/951_2.png) [@didibus](https://clojureverse.org/u/didibus)
#### Post date: [April 17, 2022, 2:48am UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/29 "2022-04-17T02:48:54Z")

</div>

> [@Josh\_Lemer](#):
>
> Do you mean, what is the point of using generators at all?

No, I mean the point of generators in this specific example? But I guess you kind of answered that as well, it is just to try for a lazy implementation? Are there other benefits though, if I don’t care about it being lazy, does generator enable anything else?

P.S: Really like that PEP, hadn’t look at a Python PEP before, well written, nice format and colors, a table of content navigation, I like the BDFL section at the end, haha, in contrast Java’s JEPs are so bare bone. Would be nice to one day have something similar for Clojure too, even if it was closed to the community, they are a nice way to see the thought process of the creators.

---

<div class="post-metadata">

### Author: ![didibus](https://clojureverse.org/user_avatar/clojureverse.org/didibus/32/951_2.png) [@didibus](https://clojureverse.org/u/didibus)
#### Post date: [April 17, 2022, 5:38am UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/30 "2022-04-17T05:38:24Z")

</div>

Also thought I give the original question a go.

Eager, and won’t blow the call-stack since I use a vector as my stack instead:

```clojure
(defn todo
  [m]
  (loop [[k v] (first m) m (next m) path [] stack [] acc []]
    (if k
      (if (map? v)
        (recur (first v) (next v) (conj path k) (conj stack {:kv (first m) :m (next m) :path path}) acc)
        (recur (first m) (next m) path stack (conj acc (conj path k) v)))
      (if (empty? stack)
        acc
        (let [{:keys [kv m path]} (peek stack)]
          (recur kv m path (pop stack) acc))))))

(todo
 {:a 99
  :x {:b 999
      :y {:z 123
          :w 456}}})
;; => [[:a] 99 [:x :b] 999 [:x :y :z] 123 [:x :y :w] 456]

```

A lazy version, for extra bonus points?

```clojure
(defn todo
  [m]
  (->>
   (iterate
    (fn [[_ kv m path stack]]
      (loop [[k v] kv m m path path stack stack]
        (if k
          (if (map? v)
            (recur (first v) (next v) (conj path k) (conj stack {:kv (first m) :m (next m) :path path}))
            (list [(conj path k) v] (first m) (next m) path stack))
          (if (empty? stack)
            nil
            (let [{:keys [kv m path]} (peek stack)]
              (recur kv m path (pop stack)))))))
    [nil (first m) (next m) [] []])
   (rest)
   (take-while seq)
   (mapcat first)))

(def t (todo {:a 99
              :b {:c {:d {:e {:f 100
                              :g 200}
                          :d 50}}}}))
(take 4 t)
;; => ([:a] 99 [:b :c :d :e :f] 100)

```

The async version is quite trivial, just swap loop for core.async go-loop. Or you could put the whole thing in a future and make it async just with future:

```auto
(defn todo
  [m]
  (a/go-loop [[k v] (first m) m (next m) path [] stack [] acc []]
    (if k
      (if (map? v)
        (recur (first v) (next v) (conj path k)
               (if-let [fm (first m)]
                 (conj stack {:kv fm :m (next m) :path path})
                 stack)
               acc)
        (recur (first m) (next m) path stack
               (conj acc (conj path k) v)))
      (if (empty? stack)
        acc
        (let [{:keys [kv m path]} (peek stack)]
          (recur kv m path (pop stack) acc))))))

(def t (todo {:a 99
              :b {:c {:d {:e {:f 100
                              :g 200}
                          :d 50}}}}))
(a/poll! t)
;; => [[:a] 99 [:b :c :d :e :f] 100 [:b :c :d :e :g] 200 [:b :c :d :d] 50]

```

I also investigated what it would take to make a concurrent asynchronous version. The above version in a `go-loop` will run synchronously and won’t yield the execution thread until it is done, so if running in Clojurescript for example, it will block any other go-block from making progress until it is done fully computing the result. In Clojure, you could just make it a `a/thread (loop ...))` or use `future` or something else that’s OS thread based, but what about Clojurescript?

Well, you could in theory try to use Web Workers or in Node use Worker Threads, that said, it seems you can introduce a simple `<!` on some channel that resolves almost instantly and that causes the go block to yield to others:

```auto
(defn yielder
  "Taking from (yielder) with <! will give go blocks a chance
   to yield themselves to other go blocks."
  []
  (a/go))

(defn todo
  [m]
  (a/go-loop [[k v] (first m) m (next m) path [] stack [] acc []]
    (println "Boy")
    (a/<! (yielder))
    (if k
      (if (map? v)
        (recur (first v) (next v) (conj path k)
               (if-let [fm (first m)]
                 (conj stack {:kv fm :m (next m) :path path})
                 stack)
               acc)
        (recur (first m) (next m) path stack
               (conj acc (conj path k) v)))
      (if (empty? stack)
        acc
        (let [{:keys [kv m path]} (peek stack)]
          (recur kv m path (pop stack) acc))))))

(todo {:a 99
       :b {:c {:d {:e {:f 100
                       :g 200}
                   :d 50}}}})
(a/go-loop [a 10]
  (a/<! (yielder))
  (when (pos? a)
    (println "Ya")
    (recur (dec a))))

```

You’ll see that in ClojureScript it will print Ya Boy in alternate-ish fashion, where-as without the yielder, it prints all the Boy and then all the Ya, meaning the Go blocks are not concurrent. This also works in Clojure to give the go block a chance to yield, though in Clojure since you have 8 threads normally you might not notice that each go block is holding a thread till completion.

Generally, the rule with go blocks is to do very little between `<!` and `>!` operations so that they can yield often and you don’t block the thread pool.

---

<div class="post-metadata">

### Author: ![system](https://clojureverse.org/uploads/default/original/2X/5/51079bf9e4b7d9466242c06cf1e43b9f8bd6da14.png) [@system](https://clojureverse.org/u/system)
#### Post date: [October 16, 2022, 5:39pm UTC](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801/31 "2022-10-16T17:39:16Z")

</div>

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.

[Previous page](https://clojureverse.org/t/how-to-transform-nested-map-into-flat-sequence-of-path-value-pairs/8801.md?page=1)