Introduction
This is a blogpost on how to use clojure.walk.
clojure.walk is incredibly powerful and definitely worth investing time into.
We’ll first look at some simple examples to get a feel for the functions and then
I’ll demonstrate its power by walking through a problem and showing two solutions, one without clojure.walk and one with.
I know the title says ‘learning to walk’, but by the end of the post you will know how to fly. That is how powerful clojure.walk is.
What is clojure.walk?
It provides three functions prewalk, postwalk, and walk which are generic tree walkers,
and also some other utility functions like prewalk-replace, and stringify-keys (I won’t be covering those in this post).
The three functions walk arbitrarily nested data structures (aka Trees). While walking the tree, they call function(s) on the nodes of the tree, and replace the nodes with the results of the function call.
prewalk
prewalk does a pre-order traversal of the tree. If you don’t know what that means, it’s fine, nothing a little demo code can’t solve.
There is a handy function called prewalk-demo that demonstrates what prewalk does.
(require '[clojure.walk :as walk])
(def tree [1 [2] [3 [4]]])
(walk/prewalk-demo tree)
; (out) Walked: [1 [2] [3 [4]]]
; (out) Walked: 1
; (out) Walked: [2]
; (out) Walked: 2
; (out) Walked: [3 [4]]
; (out) Walked: 3
; (out) Walked: [4]
; (out) Walked: 4
;=> [1 [2] [3 [4]]]
This shows the order in which the nodes of the tree are walked.
it first walks the parent node [1 [2] [3 [4]]] and then the child nodes 1, [2], etc.
Writing our own version of prewalk-demo
In order to learn how prewalk works, we can try to replicate prewalk-demo.
The args prewalk takes are [f form].
f is the function it will call on every node.
prewalk-demo prints all the values of the node as it walks them, so f must be a print function, right?
let’s try it out.
(require '[clojure.walk :as walk])
(def tree [1 [2] [3 [4]]])
(walk/prewalk (fn [x] (print "walked: " x)) tree)
; (out) walked: [1 [2] [3 [4]]]
;=> nil
Oops, what happened? Why didn’t it walk the children? Remember I said that it calls a function on the nodes and replaces the node with the result of the function call.
Since (fn [x] (print "walked: " x)) returned nil that’s why the walk terminated.
Our function f must also return the value of x.
(require '[clojure.walk :as walk])
(def tree [1 [2] [3 [4]]])
(walk/prewalk (fn [x] (print "walked: " x "\n") x) tree)
; (out) walked: [1 [2] [3 [4]]]
; (out) walked: 1
; (out) walked: [2]
; (out) walked: 2
; (out) walked: [3 [4]]
; (out) walked: 3
; (out) walked: [4]
; (out) walked: 4
;=> [1 [2] [3 [4]]]
The important thing to remember is that prewalk walks the result of calling f on a node.
If f returns nil, the walk for that branch terminates.
postwalk
postwalk is like prewalk but does a post-order traversal. It visits the child nodes first, calling f on the child nodes,
replacing the child nodes with the result of (f child).
and then visits the parent nodes calling f on them.
(require '[clojure.walk :as walk])
(def tree [1 [2] [3 [4]]])
(walk/postwalk-demo tree)
; (out) Walked: 1
; (out) Walked: 2
; (out) Walked: [2]
; (out) Walked: 3
; (out) Walked: 4
; (out) Walked: [4]
; (out) Walked: [3 [4]]
; (out) Walked: [1 [2] [3 [4]]]
;=> [1 [2] [3 [4]]]
Writing our own version of postwalk-demo
You probably already know how to solve this, but let’s pretend we don’t know.
(require '[clojure.walk :as walk])
(def tree [1 [2] [3 [4]]])
(walk/postwalk (fn [x] (print "walked: " x "\n")) tree)
; (out) walked: 1
; (out) walked: 2
; (out) walked: [nil]
; (out) walked: 3
; (out) walked: 4
; (out) walked: [nil]
; (out) walked: [nil nil]
; (out) walked: [nil nil nil]
;=> nil
isn’t the result interesting? the walk didn’t terminate prematurely like it did in prewalk.
But the last printed out value is a vector of nils.
That’s because postwalk visits the children first. print replaces the child nodes with nil and that’s
why you see a vector of nils printed out last.
Since you know how to actually fix it, I won’t waste your time.
Why prewalk and postwalk might feel confusing at first.
If you’re used to the way trees are defined in java or python, you might find clojure trees confusing. Especially the tree walking functions. Before I can try to explain why that is, I’d like to take a detour into lisp’s syntax.
Lisp’s notion of atoms and lists
Lisp is made up of s-expressions, and s-expressions in turn are made up of lists and atoms. Lists are simple to identify, if it is protected by parentheses, it’s a list. Atoms are everything else.
Lists are made up of atoms, or other lists. Atoms are well, made up of themselves, and can’t contain other atoms. They are “indivisible”. A number or symbol is an atom.
Note: In the entire post, when I talk about atoms I’m not talking about clojure’s atom but rather lisp’s atom.
A helpful way to distinguish between them is that lists are iterable and atoms are non-iterable.
Strings are well… special
Strings are sequences of characters. They are lists, not atoms. You can call all sequence functions on strings.
(first "a-string") ; \a
(rest "a-string") ; (\- \s \t \r \i \n \g)
(map identity "a-string") ; (\a \- \s \t \r \i \n \g)
but clojure.walk treats them as non-iterable.
(prewalk-demo [1 [2 3] "a-string"])
; (out) Walked: [1 [2 3] "a-string"]
; (out) Walked: 1
; (out) Walked: [2 3]
; (out) Walked: 2
; (out) Walked: 3
; (out) Walked: "a-string"
;=> [1 [2 3] "a-string"]
it doesn’t iterate through "a-string".
you could convert "a-string" to a seq to see the difference
(prewalk-demo [1 [2 3] (seq "a-string")])
; (out) Walked: [1 [2 3] (\a \- \s \t \r \i \n \g)]
; (out) Walked: 1
; (out) Walked: [2 3]
; (out) Walked: 2
; (out) Walked: 3
; (out) Walked: (\a \- \s \t \r \i \n \g)
; (out) Walked: \a
; (out) Walked: \-
; (out) Walked: \s
; (out) Walked: \t
; (out) Walked: \r
; (out) Walked: \i
; (out) Walked: \n
; (out) Walked: \g
[1 [2 3] (\a \- \s \t \r \i \n \g)]
Lists are non-leaf-nodes and atoms are leaf nodes.
The whole point of bringing up lisp’s syntax was to have a common vocabulary.
A leaf node in a tree is a node that can’t be traversed further, it’s a dead end.
non-leaf nodes can be traversed further.
If you see the definition of walk, you’ll notice that it checks if the form (node) is a collection (list),
if it is, calls map on it (or iterates over it in some way)
if it is not a list-type, then it just calls the outer function on it. and doesn’t traverse it further.
note: i have commented out parts of the code, as I want to draw attention to specific parts of it.
;; warning this code doesn't run due to unbalanced parentheses
;; taken from clojure.walk source code
(defn walk
"Traverses form, an arbitrary data structure. inner and outer are
functions. Applies inner to each element of form, building up a
data structure of the same type, then applies outer to the result.
Recognizes all Clojure data structures. Consumes seqs as with doall."
{:added "1.1"}
[inner outer form]
(cond
(list? form)
; (outer (apply list
(map inner form)))
;; (instance? clojure.lang.IMapEntry form)
;; (outer (clojure.lang.MapEntry/create (inner (key form)) (inner (val form))))
(seq? form)
; (outer (doall
(map inner form)))
;; (instance? clojure.lang.IRecord form)
;; (outer (reduce (fn [r x] (conj r (inner x))) form form))
(coll? form)
; (outer (into (empty form)
(map inner form)))
:else (outer form)))
Since the traversal terminates when the node is not a list-type, atoms make up leaf-nodes and lists make up other nodes. The only exception is that a string is treated as a leaf node.
OOP-style trees.
A node has a value, and a reference to other nodes (child nodes). A common way to define a tree node is like this.
class Node:
def __init__(self, value, children:list=[]):
self.value=value
self.children = children
The node holds a value, and a reference to its child nodes.
When we visit a node, we operate on its value and then traverse the child nodes.
if we did a pre_walk and post_walk of a node, printing our visitation as we go, it would look something like this
class Node:
def __init__(self, value, children:list=[]):
self.value=value
self.children = children
def pre_walk(tree):
print(tree.value)
for child in tree.children:
pre_walk(child)
if __name__=="__main__":
tree = Node(1, [Node(2), Node(3, [Node("A"), Node("B") ]), Node(4)])
# tree
# 1
# / | \
# 2 3 4
# / \
# A B
pre_walk(tree)
# 1
# 2
# 3
# A
# B
# 4
post_walk(tree)
# 2
# A
# B
# 3
# 4
# 1
In this type of a tree, the value of a node is not it’s subtree, it is separately defined.
Contrast this to the clojure way of doing the same thing
(prewalk-demo [1 [2 [3 "A" "B"] 4]])
; (out) Walked: [1 [2 [3 "A" "B"] 4]]
; (out) Walked: 1
; (out) Walked: [2 [3 "A" "B"] 4]
; (out) Walked: 2
; (out) Walked: [3 "A" "B"]
; (out) Walked: 3
; (out) Walked: "A"
; (out) Walked: "B"
; (out) Walked: 4
[1 [2 [3 "A" "B"] 4]]
(postwalk-demo [1 [2 [3 "A" "B"] 4]])
; (out) Walked: 1
; (out) Walked: 2
; (out) Walked: 3
; (out) Walked: "A"
; (out) Walked: "B"
; (out) Walked: [3 "A" "B"]
; (out) Walked: 4
; (out) Walked: [2 [3 "A" "B"] 4]
; (out) Walked: [1 [2 [3 "A" "B"] 4]]
[1 [2 [3 "A" "B"] 4]]
Clojure’s walk treats a list as a node, and its element as nodes. so when you walk the tree, you might expect it to only print the numbers or strings. but it also prints the vector (list) because that is the value of the node. The value of a non-leaf node is its entire SUBTREE. This tripped me up a lot when I first encountered clojure.walk.
Remember-
leaf nodes are atoms (& strings). non-leaf nodes are lists.
Getting a feel for the difference between prewalk and postwalk
As you saw, the same print function, on the same tree, produced a vastly different result based on whether you used prewalk or postwalk.
Here are some examples to get a feel for the difference.
Example #1
The common function for both will append 777 if the the current node is a vector, else it will increment the number.
(defn append-or-inc
[x]
(if (vector? x)
(conj x 777)
(inc x)))
Let’s see prewalk in action
(require '[clojure.walk :as walk])
(defn append-or-inc
[x]
(if (vector? x)
(conj x 777)
(inc x)))
(def tree [1 [2] [3 [4]]])
(walk/prewalk append-or-inc tree)
;=> [2 [3 778] [4 [5 778] 778] 778]
now let’s see postwalk in action
(require '[clojure.walk :as walk])
(defn append-or-inc
[x]
(if (vector? x)
(conj x 777)
(inc x)))
(def tree [1 [2] [3 [4]]])
(walk/postwalk append-or-inc tree)
;=> [2 [3 777] [4 [5 777] 777] 777]
If we compare the results, the only difference is that 777 was incremented in prewalk, but not postwalk.
[2 [3 778] [4 [5 778] 778] 778] ; prewalk
[2 [3 777] [4 [5 777] 777] 777] ; postwalk
This is because when doing the prewalk we visited the parent node first, created a new child node (i.e 777)
and then visited all the child nodes, which now included 777.
But in postwalk we visited the child nodes (which didn’t include 777) and incremented them and then visited the parent node,
and created a new child node (777), so the child node (777) we created was never visited and thus was not incremented.
Example #2
We will use str as the common function.
(walk/prewalk str tree) ; "[1 [2] [3 [4]]]"
(walk/postwalk str tree) ; "[\"1\" \"[\\\"2\\\"]\" \"[\\\"3\\\" \\\"[\\\\\\\"4\\\\\\\"]\\\"]\"]"
The results are wildly different.
in the case of prewalk, str was called on [1 [2] [3 [4]]] and it returned a string terminating the walk.
But in the case of postwalk, str was called on the children first, creating a nested vector of strings, and then
finally calling str on that vector.
Example #3
The common function for will convert the number to a string if it is even.
(defn stringify-even
[x]
(if (and (number? x)
(even? x))
(str x)
x))
Calling postwalk and prewalk
(walk/prewalk stringify-even tree) ; [1 ["2"] [3 ["4"]]]
(walk/postwalk stringify-even tree) ; [1 ["2"] [3 ["4"]]]
In this case, the results were the same.
Now, why is that? Why do some functions give us different results with prewalk and postwalk,
whereas others give the same result?
It is due to the nature of the functions- append-or-inc and str act on all the nodes in the tree,
whereas stringify-even only acts on the leaf node of the tree, and returns all other nodes unchanged.
Walking through maps
Until now we’ve looked at how walk works with sequential data-structures.
But maps are very common in clojure and walk supports maps as well, so it’s important to get comfortable with
walking maps.
(def map-tree {:a 1 :b {:c 2}})
(walk/prewalk-demo map-tree)
; (out) Walked: {:a 1, :b {:c 2}}
; (out) Walked: [:a 1]
; (out) Walked: :a
; (out) Walked: 1
; (out) Walked: [:b {:c 2}]
; (out) Walked: :b
; (out) Walked: {:c 2}
; (out) Walked: [:c 2]
; (out) Walked: :c
; (out) Walked: 2
;=>{:a 1, :b {:c 2}}
(walk/postwalk-demo map-tree)
; (out) Walked: :a
; (out) Walked: 1
; (out) Walked: [:a 1]
; (out) Walked: :b
; (out) Walked: :c
; (out) Walked: 2
; (out) Walked: [:c 2]
; (out) Walked: {:c 2}
; (out) Walked: [:b {:c 2}]
; (out) Walked: {:a 1, :b {:c 2}}
;=> {:a 1, :b {:c 2}}
If you take a closer look at the result of prewalk-demo,
you’ll notice that walk doesn’t directly visit :a and :1,
it visits [:a 1] which is a MapEntry.
Even if [:a 1] looks like a vector it is a MapEntry.
(first {:a 1 :b {:c 2}})
;=> [:a 1]
(map-entry? (first {:a 1 :b {:c 2}}))
;=> true
The types of operations you will perform on trees
The function you pass to prewalk/postwalk can operate on a subtree or a leaf-node. You can carry out 3 operations on each node.
- Adding a new subtree or leaf-node. (Expanding a tree)
- Removing a leaf-node or a subtree. (Trimming a tree)
- Changing the value of leaf-node/subtree, without modifying the number of nodes.
As a general rule of thumb-
When expanding a tree, you will use
prewalkand when trimming a tree you will usepostwalk.
If you are changing the value of the leaf node then which function you use doesn’t matter as you saw in example #3.
Adding a new subtree or leaf-node (expanding a tree)
Let’s define a function that walks a tree of symbols and tries to resolve the symbols to values (not very different from what an interpreter might do)
(def a '[1 2 3 b])
(def b '["a" "b" c])
(def c '[:a :b :c])
(def tree [1 'a ['b [2 'c]]] )
(prewalk
(fn [x]
(if (symbol? x)
(eval x) ; It's for a good cause, don't judge!
x))
tree)
; [1 [1 2 3 ["a" "b" [:a :b :c]]] [["a" "b" [:a :b :c]] [2 [:a :b :c]]]]
(postwalk
(fn [x]
(if (symbol? x)
(eval x) ; I can see your judgemental eyes.
x))
tree)
; [1 [1 2 3 b] [["a" "b" c] [2 [:a :b :c]]]]
postwalk did not expand all the symbols, it only expanded c.
[1 [1 2 3 ["a" "b" [:a :b :c]]] [["a" "b" [:a :b :c]] [2 [:a :b :c]]]] ; prewalk
[1 [1 2 3 b] [["a" "b" c] [2 [:a :b :c]]]] ; postwalk
Why is prewalk suitable for expanding trees?
If a node can expand into a tree, you would want to visit that node first, expand it and then visit its children, which can themselves expand into other trees.
(def a '[1 2 3 b])
(def b '["a" "b" c])
When prewalk encounters the symbol b in the tree a, it calls eval on it, and then walks the vector b evaluates to.
This is because the symbol b is treated as parent node (not a child node),
Whereas when postwalk encounters the symbol b, it encounters it as a child node, so calling eval on it will expand it, but since it’s
a child node, it won’t be walked, because postwalk visits the child and then the parent.
A useful mental model is to imagine prewalk as climbing UP the tree (from the root to the leaves) and postwalk as climbing DOWN the tree (from the leaves to the roots).
So when you are climbing up the tree, and are at a leaf, and the leaf “expands” into a branch, you still have more leaves to climb.
Whereas if you’re climbing down the tree, you start at the leaf, so, even if the leaf expands, you’re still headed towards the root, and you’re not going to backtrack up the new leaves and start again.
Removing a subtree (trimming a tree)
Let’s look at a function that does the opposite of what the above function did. It replaces values with its symbols.
(def a '[1 2 3 b])
(def b '["a" "b" c])
(def c '[:a :b :c])
(def tree '[1 a [b [2 c]]])
(def expanded-tree [1 [1 2 3 ["a" "b" [:a :b :c]]] [["a" "b" [:a :b :c]] [2 [:a :b :c]]]])
(prewalk (fn [x]
(if (vector? x)
(condp = x
a 'a
b 'b
c 'c
x)
x))
expanded-tree)
;=> [1 [1 2 3 ["a" "b" c]] [["a" "b" c] [2 c]]]
(postwalk (fn [x]
(if (vector? x)
(condp = x
a 'a
b 'b
c 'c
x)
x))
expanded-tree)
;=> [1 a [b [2 c]]]
prewalk only shrunk [:a :b :c] into c.
[1 [1 2 3 ["a" "b" c]] [["a" "b" c] [2 c]]] ; prewalk
[1 a [b [2 c]]] ; postwalk
Why is postwalk suitable for trimming trees?
In this case, we are replacing the subtree based on the value of the subtree.
So if you start from the bottom (prewalk), look up and try to match the subtree, it doesn’t match anything,
then you climb a level higher, try to match it, nothing, eventually you come across [:a :b :c] and say hey look,
that matches the symbol c, so let me replace that. After replacing that node with c, the whole tree looks different.
but since you are already at the leaf nodes, and you’re ONLY climbing up, you don’t see the new tree.
Whereas in postwalk, you start at the top, look at [:a :b :c], say it matches c, replace it and then climb down.
then you’ll see ["a" "b" 'c] and say, hey look that’s b and replace it with b, so on and so forth.
Another way to think of it is, if you are only going to climb up a tree, and you have to cut the tree at a branch, you can only cut that branch, and the branches above it, you can’t cut a branch and then go down and cut the branches below (because you’re only going up).
A real world example.
Recently at work a colleague of mine wanted to write a function that
recursively removed keys from a map if the value of the key was nil or an empty collection.
The collections can be of different types like vectors, sets, and even maps.
The function must preserve the original type of the datastructure.
This was my solution, which is ugly, inelegant and verbose, but it works.
(defn conj-map-if-not-empty
[coll m]
(if-not (empty? (first (vals m)))
(conj coll m)
coll))
(defn conj-if-not-empty
[coll x]
(if (and (seq? x)
(empty? x))
coll
(conj coll x)))
(declare clean-map)
(defn clean-coll
([coll]
(clean-coll coll ()))
([coll accum]
(reduce (fn [acc x]
(cond
(nil? x) acc
(and (seq? x)
(empty? x)) acc
(map? x) (conj acc (clean-map x))
(vector? x) (conj-if-not-empty acc (clean-coll x []))
(seq? x) (conj-if-not-empty acc (clean-coll x ()))
(set? x) (conj-if-not-empty acc (clean-coll x #{}))
:else (conj acc x)))
accum
coll)))
(defn clean-map
[m]
(reduce-kv (fn [acc k v]
(cond
(nil? v) acc
(and (seq? v)
(empty? v)) acc
(map? v) (conj-map-if-not-empty acc {k (clean-map v)})
(vector? v) (conj-map-if-not-empty acc {k (clean-coll v [])})
(seq? v) (conj-map-if-not-empty acc {k (clean-coll v ())})
(set? v) (conj-map-if-not-empty acc {k (clean-coll v #{})})
:else (conj acc {k v})))
{}
m))
This was before I knew how to use clojure.walk.
Do you know how big the actual solution was? 14 lines (with proper indentation and spacing)! I will walk (haha) you through how you might solve this problem.
Step 1 - Figure out whether clojure.walk is suitable
You know we are going to use clojure.walk because this is a post about that.
But let’s take a step back and tease out the characteristics of this problem that make it a good fit.
The problem statement says that the function is recursive (that’s the first clue), because recursive
functions usually work with arbitrarily nested data-structures, the second thing is that it can contain other collections,
and their type must be preserved.
clojure.walk preserves the type of the collection it traversers.
These two characteristics (arbitrarily nested and heterogenous data-structures whose types need to be preserved) are good signs that clojure.walk is a good fit.
And if it isn’t a good fit, you could always try something else, don’t waste too much time on this.
Step 2 - Determine whether you need prewalk or postwalk
The problem statement indicates that you want to replace nils and empty collections.
Aha so you’re trimming the tree, which means you need to use postwalk.
Step 3 figuring out the operations
Generally speaking, you will either operate on the list or the atom, this is rather straightforward with collections that are not maps. When it comes to maps, you can operate on 3 things - the map, the map entry, or the key or value.
Remember that your function will be called at every step of postwalk, and you can make decisions at every step.
The various steps would be -
(prewalk-demo [1])
; (out) Walked: [1] ; a
; (out) Walked: 1 ; b
(prewalk-demo {:a 1})
; (out) Walked: {:a 1} ; c
; (out) Walked: [:a 1] ; d
; (out) Walked: :a ; e
; (out) Walked: 1 ; f
We want to do 2 things in our function
- Remove a key/value pair if the value is nil or an empty collection.
- Remove nil values from a vector/list/set etc.
For #1 we can make that decision when we get a MapEntry (see d in the code above) and for #2 we can transform it when we get a collection (see a in the code above)
(fn [x]
(cond
;; branch 1
(map-entry? x)
(let [v (val x)]
(if (or (nil? v)
((every-pred empty? coll?) v))
nil
x))
;; branch 2
(coll? x)
(into (empty x) ; (empty x) because we want to preserve the type of the collection
(remove #(or (nil? %)
((every-pred empty? coll?) %))
x))
:else x))
This function works fine, but we can simplify it a little more. The function is doing two different things in two different cases, which operation will happen first? branch 2 or branch 1?
if you’re unsure, you can always use postwalk-demo to figure it out.
(postwalk-demo {:a [1 nil]})
; (out) Walked: :a
; (out) Walked: 1
; (out) Walked: nil
; (out) Walked: [1 nil]
; (out) Walked: [:a [1 nil]]
; (out) Walked: {:a [1 nil]}
Your function will first encounter :a, then 1, then nil, then the vector [1 nil] and then the MapEntry [:a [1 nil]].
Branch 2 will be hit before branch 1.
Since we are already removing nils and empty collections in branch 2, we don’t need to check for that in branch 1.
(fn [x]
(cond
(map-entry? x)
(if (nil? (val x)) ;; new
nil
x)
(coll? x)
(into (empty x)
(remove #(or (nil? %)
((every-pred empty? coll?) %))
x))
:else x))
We are not done yet, I’m not a big fan of the (every-pred empty? coll?) check.
We can use the not-empty function to return the collection as it is if it’s not-empty, else return nil.
(fn [x]
(cond
(map-entry? x)
(if (nil? (val x))
nil
x)
(coll? x)
(not-empty (into (empty x) ;; new
(remove nil?
x)))
:else x))
And we are done, this function is only 12 lines long!!!
and it works!
(postwalk (fn [x]
(cond
(map-entry? x)
(if (nil? (val x)) ; new
nil
x)
(coll? x)
(not-empty (into (empty x)
(remove nil?
x)))
:else x))
{:a 1
:b [1 2 [nil] []]
:c {:d :a
:e {:f nil}
:g #{1 2}
:h #{nil}
:i ()}
:z {}})
;=> {:a 1, :b [1 2], :c {:d :a, :g #{1 2}}}
P.S this is slightly different from what my colleague came up with. He removed nils from a map using remove.
This was his solution.
; credits to Joel Victor
(fn
[x]
(cond
(map? x)
(not-empty (into {}
(remove (comp nil? val))
x))
(map-entry? x) x
(coll? x) (not-empty (into (empty x)
(remove nil?)
x))
:else x))
A real world example of prewalk
An excellent usecase of prewalk is clojure.walk/macroexpand-all.
;; taken from clojure.walk
(defn macroexpand-all [form]
(prewalk (fn [x]
(if (seq? x)
(macroexpand x)
x))
form))
Remember, you use prewalk when you’re expanding the tree.
What about clojure.walk/walk?
walk is a rather interesting function. At its heart, it does something like this
;; this is a gross oversimplification of the walk function
;; you can read that actual source if you like, it's small enough
(defn walk
[inner outer form]
(if (coll? form)
(outer (map inner form))
(outer form)))
This absolutely simple pattern can let you build custom tree traversal functions.
Practically speaking, you’re not likely to reach for walk, you’ll most likely be using prewalk or postwalk.
But just in case you were curious, here’s a custom tree traversal function.
OOP-style trees
Remember I mentioned oop-style trees, we can create them in clojure as well.
(def tree
{:value 1
:children [{:value 2
:children [{:value 4
:children []}]}
{:value 3
:children [{:value 5
:children []}]}]})
Using walk we can write prewalk and postwalk versions for oop-style trees.
For prewalk we visit the parent node first and then its children
(defn prewalk-oop-tree
[f tree]
(-> tree
(update :value f) ; update the parent value
(update :children #(walk (partial prewalk-oop-tree f) ; say hi to the children
identity
%))))
(prewalk-oop-tree #(do (prn %) %) tree)
; (out) 1
; (out) 2
; (out) 4
; (out) 3
; (out) 5
;=>
{:value 1,
:children
[{:value 2, :children [{:value 4, :children []}]}
{:value 3, :children [{:value 5, :children []}]}]}
postwalk is easy, just swap the order of the updates and you’re done.
(defn postwalk-oop-tree
[f tree]
(-> tree
(update :children #(walk (partial postwalk-oop-tree f)
identity
%))
(update :value f)))
(postwalk-oop-tree #(do (prn %) %) tree)
; (out) 4
; (out) 2
; (out) 5
; (out) 3
; (out) 1
{:value 1,
:children
[{:value 2, :children [{:value 4, :children []}]}
{:value 3, :children [{:value 5, :children []}]}]}
Closing thoughts
It was quite hard for me to wrap my head around the clojure.walk family of functions, and it will take you time as well.
Struggle with it but stay with it.
I still find walk quite hard to grasp and use.
It’s a very useful tool in your toolbox.
Once you get comfortable with them, you’ll start recognizing patterns and would immediately be able to use these functions.
These functions can lead to elegant and beautiful solutions. You saw that the solution to the problem of removing nils and empty collections without postwalk was verbose, and plain ugly, I knew it was ugly even when I wrote it.
With that said, this is a two-way street, if you find mistakes, typos, or have suggestions, (or even compliments xD) please tweet at me @the_lazy_folder or email me. I love listening to y’all.