Functional JavaScript: Traversing Trees with a Recursive Reduce
Trees come up a lot in web development. More than you would expect, anyway. For most of my web development career, I haven’t needed many complicated data structures. And tricky algorithms don’t come up that often either. Things like linked lists and travelling salesmen don’t appear all that often on the front end. Not that knowing about them isn’t useful. But trees…. Trees are an exception. They just keep popping up.
It’s not so surprising, really. The DOM is a tree. HTML has a hierarchical structure. Menus tend to have hierarchical structures too. Early websites were based on the old file/folder metaphor, so it all makes sense. But when you start looking for them, there’s tree structures all over the place.
But trees can be tricky. If you’re like me, you know that there ought to be a way to process them neatly. You might want to change all the values, or make some calculation. But the way to do it isn’t always obvious. And utility libraries like Ramda and Lodash don’t come with tree-traversing functions. So we’re stuck rolling our own.
With a few minor tweaks though, we can use our old friends map() and reduce() to help us out. Then we can process trees just as easily as we do arrays (with some caveats, as we’ll see).
A Sample Problem.
Let’s look at a sample problem. Imagine we have a menu structure:
const menu = [
{
type: 'title',
text: 'Works of George Macdonald',
},
{
type: 'link',
href: '/books',
text: 'Books',
},
{
type: 'link',
href: '/poetry',
text: 'Poems',
},
{
type: 'link',
href: '/essays',
text: 'Essays',
},
{
type: 'title',
text: 'Our Community',
},
{
type: 'link',
href: '/about',
text: 'About us',
}
{
type: 'link',
href: '/forum',
text: 'Forum',
},
{
type: 'link',
href: 'https://www.facebook.com/groups/GeorgeMacDonaldCommunity/',
text: 'Facebook Group',
},
];
With an array like this it’s not so hard to calculate the number of links. We could even do it in just a few lines:
function sumLinks(total, item) {
return total + ((item.type === 'link') ? 1 : 0);
}
const numLinks = menu.reduce(sumLinks, 0);
But what if our menu had more levels?
const menu = {
type: 'title',
text: 'Menu',
children: [
{
type: 'title',
text: 'Works of George Macdonald',
},
{
type: 'link',
href: '/books',
text: 'Books',
children: [
{
type: 'link',
href: '/books/sir-gibbie',
text: 'Sir Gibbie',
},
{
type: 'link',
href: '/books/at-the-back-of-the-north-wind',
text: 'At the Back of the North Wind',
},
{
type: 'link',
href: '/books/the-princess-and-the-goblin',
text: 'The Princess and the Goblin',
},
]
},
{
type: 'link',
href: '/poetry',
text: 'Poems',
},
{
type: 'link',
href: '/essays',
text: 'Essays',
children: [
{
type: 'link',
href: '/essays/the-fantastic-imagination',
text: 'The Fantastic Imagination',
},
{
type: 'link',
href: '/essays/the-new-name',
text: 'The New Name',
},
]
},
{
type: 'title',
text: 'Our Community',
},
{
type: 'link',
href: '/about',
text: 'About us',
children: [
{
type: 'link',
href: '/about/membership',
text: 'Community membership',
},
{
type: 'link',
href: '/about/sponsorship',
text: 'Community sponsorship',
children: [
{
type: 'link',
href: '/about/sponsorship/patreon',
text: 'Our Patreon',
},
{
type: 'link',
href: '/about/sponsorship/endowments',
text: 'Endowments',
},
]
},
]
},
{
type: 'link',
href: '/forum',
text: 'Forum',
},
{
type: 'link',
href: 'https://www.facebook.com/groups/GeorgeMacDonaldCommunity/',
text: 'Facebook Group',
},
]
};
Here, the answer isn’t so obvious. JavaScript lets us create tree-like structures easily enough. We can stick objects inside arrays, and arrays inside objects. But there’s no real concept of a Tree type provided by JavaScript. So, there’s no Tree.prototype.map() or Tree.prototoype.reduce(). We’re on our own.
Even turning back to the old ways of imperative loops won’t help us. Sacrificing an iterator variable to the browser gods won’t solve our problem. Not even if we call it i. We need another set of tools.
Map and reduce for trees
What we want is something like Array.prototype.reduce() and Array.prototype.map(). But we’d want them to work on tree structures like the ones above. Then, we could work with tree structures just as easily as we work with arrays.
So, how do we go about it? Well, if we look at the tree structure, we can see that it’s a little bit repetitive. Sub-branches of the tree share much the same structure as the top-level of the tree. That is, items in children a lot like the parent structure. They’re both objects, sometimes with a children attribute. Whenever we see repetition like this, the solution will often involve recursion. At least, it’s a good place to start looking anyway.
We get recursion when a function calls itself inside the function definition. It’s kind of mind boggling when you first encounter it. But it’s really handy for working with things like trees.
There is one rule you should always remember with recursion though: Always know how you will stop. How will we know to stop processing an object in a tree structure? Well, if it doesn’t have any children, then we can’t go any further. So, with our sample data structure, it’s pretty simple. We can write a simple function that will do the check for us:
function hasChildren(node) {
return (typeof node === 'object')
&& (typeof node.children !== 'undefined')
&& (node.children.length > 0);
}
We’d like to call our function reduce, but we don’t want it to be confused with Array.prototype.reduce(). So we’ll stick it in an object to make it clear. And while we’re at it, we’ll curry our function to make composition easier. There’s a good reason for this, which we’ll see in a minute…
// Import a curry function
import {curry} from 'ramda';
const Tree = {
reduce: curry(function reduce(init, reducerFn, tree) {
// Code to do reduce goes here
}),
}
Now, if we’re processing a leaf node, it’s pretty clear what we need to do. We just call the reducer function and return the result:
const Tree = {
reduce: curry(function reduce(reducerFn, init, node) {
// Calculate the reduced value for this node.
const acc = reducerFn(init, node);
if (!hasChildren(node)) {
return acc;
}
// But what if there are children?
}),
}
But for now, our reducer is able to process leaf nodes. If there’s no children, we apply the reducer function and return the value. But what do we do if the node does have children?
If there are children, then we need to process a whole array of subtrees. Fortunately, we know how to reduce arrays. And here’s where the currying comes in. Our Tree.reduce function has a signature that looks something like this:
Tree.reduce :: (Function, a, Object) -> a
-- where a represents any type
That is, Tree.reduce() takes a Function, *something, and an Object. And it returns something the same type as our second parameter. If we partially apply the first parameter (reducerFn), then the signature becomes:
PartiallyAppliedReduce :: (a, Object) -> a
And that happens to look a lot like the signature of a reducer function… So, we can do something like this:
const Tree = {
reduce: curry(function reduce(reducerFn, init, node) {
const acc = reducerFn(init, node);
if (!hasChildren(node)) {
return acc;
}
return node.children.reduce(Tree.reduce(reducerFn), acc);
}),
}
With that in place, we could count the links in our menu like so:
function sumLinks(total, item) {
return total + ((item.type === 'link') ? 1 : 0);
}
console.log(Tree.reduce(sumLinks, 0, menu));
Now, what did we change to make sumLinks() work with Tree.reduce()? That’s right—absolutely nothing. All the complexity of dealing with a tree structure is buried inside Tree.reduce().
So, we could create other reducers that work just as easily with reduce. For example, if we wanted to flatten our tree structure to an array:
function flattenToArray(arr, {children, ...data}) {
return arr.concat([{...data}]);
}
console.log(Tree.reduce(flattenToArray, [], menu));
What if we wanted to modify our tree though? Say, what if we wanted to modify the text element and show how many children each item has? We’d want to do something like map over the tree, and return a new tree. It might look something like this:
const Tree = {
reduce: curry(function reduce(reducerFn, init, node) {
const acc = reducerFn(init, node);
if (!hasChildren(node)) {
return acc;
}
return node.children.reduce(Tree.reduce(reducerFn), acc);
}),
map: curry(function map(mapFn, node) {
const newNode = mapFn(node);
if (hasChildren(node)) {
return newNode;
}
newNode.children = node.children.map(Tree.map(mapFn));
return newNode;
}),
};
We’ve curried our function again. That makes it easier to call Tree.map() recursively as we traverse over the children. In general, it doesn’t look so very different from our Tree.reduce() function.
Then, to count the children and add the new text, we write a map function:
function addChildCount(node) {
const countstr = (hasChildren(node)) ? ` (${node.children.length})` : '';
return {
...node,
text: node.text + countstr,
}
}
console.log(Tree.map(addChildCount, menu));
Or, perhaps we need to go through and change all the links so they’re fully qualified domain names (FQDNs). We could do something like this:
const prependHost = curry(function prependHost(host, node) {
if (node.type !== 'link') { return node; }
return {
...node,
href: node.href.replace(/^\//, host),
}
});
console.log(Tree.map(prependHost('http://example.com/'), menu));
Working with DOM trees
This is all well and good, but perhaps this still seems a little contrived. What about something more real world? How about something that actually involves working with the DOM and manipulating stuff on a web page? It might look something like this:
<nav>
<h2>Menu</h2>
<ul>
<li><h3>Works of George Macdonald</h3></li>
<li>
<a href="/books">Books</a>
<ul>
<li><a href="/books/sir-gibbie">Sir Gibbie</a></li>
<li><a href="/books/at-the-back-of-the-north-wind">At the Back of the North Wind</a></li>
<li><a href="/books/the-princess-and-the-goblin">The Princess and the Goblin</a></li>
</ul>
</li>
<li><a href="/poetry">Poems</a></li>
<li>
<a href="/essays">Essays</a>
<ul>
<li><a href="/essays/the-fantastic-imagination">The Fantastic Imagination</a></li>
<li><a href="/essays/the-new-name/">The New Name</a></li>
</ul>
</li>
<li><h3>Our Community</h3></li>
<li>
<a href="/about">About us</a>
<ul>
<li><a href="/about/membership">Community membership</a></li>
<li>
<a href="/about/sponsorship">Community sponsorship</a>
<ul>
<li><a href="/about/sponsorship/patreon">Our Patreon</a></li>
<li><a href="/about/sponsorship/endowment">Endowments</a></li>
</ul>
</li>
</ul>
</li>
<li><a href="/forum">Forum</a></li>
<li><a href="https://www.facebook.com/groups/GeorgeMacDonaldCommunity">Facebook Group</a></li>
</ul>
</nav>
Now, our tree functions won’t work properly on the DOM without modification. This is because the children property of a DOM element is not an array. It’s an HTMLCollection. That means it does not have a .reduce() method or a .map() method.
Replacing the array .reduce() is fairly easy. We can just borrow the Array.prototype version and the JS engine will figure it out for us. But we have to tweak our hasChildren() function a little bit first:
function hasChildren(node) {
return (typeof node === 'object')
&& (typeof node.childNodes !== 'undefined')
&& (node.childNodes.length > 0);
}
const DOMTree = {
reduce: curry(function reduce(reducerFn, init, node) {
const acc = reducerFn(init, node);
if (!hasChildren(node)) { return acc; }
const children = node.childNodes;
return [...children].reduce((a, x) => DOMTree.reduce(reducerFn, a, x), acc);
}),
// Modified map function will go here.
};
Tweaking our Tree.map() function is a little bit trickier. For two reasons:
- Like with
.reduce(), thechildrenattribute is anHTMLCollection, so it does not have a.map()method; and - When working with the DOM have to hold our nose and accept that we’re going to end up mutating things.
Discussing functional programming and the DOM is enough for a whole series of blog posts. Not to mention that I’m still thinking through the best way to approach it myself. But for now, let’s see what we can do to make our Tree.map() method do something useful.
For now, we’ll have to accept that our method will operate more like .forEach() than .map(). The key difference being that we will return the mutated DOM element at the end. Here’s how Tree.map() might work for DOM elements:
const DOMTree = {
reduce: curry(function reduce(reducerFn, init, node) {
console.log({node});
const acc = reducerFn(init, node);
if (!hasChildren(node)) { return acc; }
const children = node.childNodes;
return [...children].reduce((a, x) => DOMTree.reduce(reducerFn, a, x), acc);
}),
map: curry(function map(fn, node) {
node = fn(node);
if (!hasChildren(node)) {
return node;
}
[...node.children].forEach(DOMTree.map(fn));
return node;
}),
};
What can we do with these shiny new functions? Well, we could do the same things we did before. We could count the number of links:
function isLink(node) {
return (node.tagName === 'A');
}
function sumLinks(total, item) {
return total + isLink(item) ? 1 : 0);
}
console.log(DOMTree.reduce(sumLinks, 0, nav));
And we could add a count of children to each link:
function addChildCount(node) {
if (!isLink(node)) { return node; }
const list = node.parentNode.querySelector('ul');
const childCount = (list) ? list.children.length : 0;
if (childCount > 0) {
node.innerHTML += ` (${childCount})`;
}
return node;
}
DOMTree.map(addChildCount, nav);
Of course, I don’t recommend doing this in practice. The DOM already comes with a bunch of utility functions that will usually be faster. For example, we could find the number of links just as easily with:
console.log(document.querySelectorAll('a').length);
And we could add a count of children to each link with something like this:
function addChildCount(node) {
if (!isLink(node)) { return node; }
const list = node.parentNode.querySelector('ul');
const childCount = (list) ? list.children.length : 0;
if (childCount > 0) {
node.innerHTML += ` (${childCount})`;
}
return node;
}
[...nav.querySelectorAll(a)].forEach(addChildCount);
In most cases, you’ll find that using the built-in DOM tools is faster and easier. So it’s rare that we’ll want to be rolling our own Tree functions (for the DOM, anyway). But, there are times when the built-in DOM tools won’t cut it. For example, what if we wanted an array of all the text nodes in our navigation structure? There’s no CSS selector for text nodes, so we can’t use .querySelectorAll(). But we could do it with Tree.reduce():
function appendTextNode(arr, node) {
return (node.nodeName === '#text') ? arr.concat([node]) : arr;
}
console.log(DOMTree.reduce(appendTextNode, [], nav));
So, no, DOMTree.reduce() and DOMTree.map() are not some silver bullet to magic away all your DOM coding troubles. But Tree and DOMTree do give you a pattern for dealing with tree structures in general. And tree structures come up quite a lot in front-end development. They’re handy patterns to have in your tool chest.