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:
(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?
(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:
(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:
(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.