# Clojure: flattening key paths

This article will cover how to flatten the nested key paths of a map in Clojure; turning a nested map like `{:a {:b {:c {:d 1} :e 2}}}` into a flat map like `{:a-b-c-d 1 :a-b-e 2}`.

## Flattening key paths recursively

We `map` over the key value pairs of the top level map. If we encounter a `map?` that is `not-empty`, we `conj` the current key onto a vector, thus gradually building a path and then call `flatten-paths` recursively. If we encounter anything else, we take the current path and turn it into a single key:

``````(defn flatten-paths
([m separator]
(flatten-paths m separator []))
([m separator path]
(->> (map (fn [[k v]]
(if (and (map? v) (not-empty v))
(flatten-paths v separator (conj path k))
[(->> (conj path k)
(map name)
(clojure.string/join separator)
keyword) v]))
m)
(into {}))))
``````

This works for shallow maps:

``````(flatten-paths {:a {:b {:c {:d 1}
:e 2}}
:f 3}
"-")

=> {:a-b-c-d 1, :a-b-e 2, :f 3}
``````

But does it work with deeply nested maps? To check this we first need to write a function `create-n-nested-map` that will create a deeply nested map:

``````(defn create-n-nested-map [n]
(assoc-in {} (repeat n :a) {}))
``````

And a harness `find-when-overflow-occurs` to tell us roughly at what depth we get a `StackOverflowError`:

``````(defn find-when-overflow-occurs [f n]
(if (try
(f n)
(catch StackOverflowError e
false))
(recur f (inc n))
n))

(find-when-overflow-occurs
(flatten-paths (create-n-nested-map n) "-")
0)

=> 599
``````

On my machine I get a stack overflow at a depth of 600. In practice, you are unlikely to encounter a map that is this deeply nested. However, lets see if we can refactor `flatten-paths` to use the sequence abstraction so that it can handle deeper maps.

## Flattening key paths with lazy-seq

The `lazy-seq` takes a body of expressions that returns an `ISeq` or `nil` and yields a `Seqable` object that will invoke the body only the first time `seq` is called. It will cache the result and return it on all subsequent seq calls. The caching of the body is what allows the `lazy-seq` macro to call itself recursively without consuming more stackframes the way a normal recursive call would.

We use `lazy-seq` to define a function that recursively builds a list of the flattened key paths. The use of `(when-let [[x & xs] (seq s)] ...)` is a common pattern when building lazy sequences, allowing you to apply a function to the head of the sequence and then call it recursively on the tail. It's also worth noting that to combine the output of the head and the tail operations we use `into` (strict) rather than `concat` (lazy). For more details check out this article.

``````(defn flatten-paths [m separator]
(letfn [(flatten-paths [m separator path]
(lazy-seq
(when-let [[[k v] & xs] (seq m)]
(cond (and (map? v) (not-empty v))
(into (flatten-paths v separator (conj path k))
(flatten-paths xs separator path))
:else
(cons [(->> (conj path k)
(map name)
(clojure.string/join separator)
keyword) v]
(flatten-paths xs separator path))))))]
(into {} (flatten-paths m separator []))))

(flatten-paths (create-n-nested-map 1000000) "-")

=>
Execution error (StackOverflowError) at user/flatten-paths...

``````

But for some reason we are still getting a `StackOverflowError`. Maybe it's our `create-n-nested-map` function that's the culprit?

``````(find-when-overflow-occurs
create-n-nested-map
0)

=> 5889
``````

Interesting... so `assoc-in` seems to be the cause. I guess this highlights just how unlikely you are to encounter such ridiculously nested maps. Let's rewrite `create-n-nested-map` to build the map from the inside out with `reduce` rather than outside in with `assoc-in`.

``````(defn create-n-nested-map [n]
(reduce (fn [acc _] {:a acc}) {} (range n)))
``````

Let's see if that works. Warning! The output is quite large and will flood your repl.

``````(flatten-paths (create-n-nested-map 1000000) "-")

=> {:a-a-a-a-a-a... {}}
``````

Rejoice! We can now flatten the key paths of ridiculously deeply nested maps.

This concludes this guide to flattening key paths in Clojure.