Examples for _.walk
===================
The _.walk module (underscore.collections.walk.js) provides implementations of
the [Underscore collection functions](http://underscorejs.org/#collections)
that are specialized for operating on nested JavaScript objects that form
trees.
Basic Traversal
—————
The most basic operation on a tree is to iterate through all its nodes, which
is provided by `_.walk.preorder` and `_.walk.postorder`. They can be used in
much the same way as [Underscore’s ‘each’ function][each]. For example, take
a simple tree:
[each]: http://underscorejs.org/#each
var tree = {
‘name’: { ‘first’: ‘Bucky’, ‘last’: ‘Fuller’ },
‘occupations’: [‘designer’, ‘inventor’]
};
We can do a preorder traversal of the tree:
_.walk.preorder(tree, function(value, key, parent) {
console.log(key + ‘: ‘ + value);
});
which produces the following output:
undefined: [object Object]
name: [object Object]
first: Bucky
last: Fuller
occupations: designer,inventor
0: designer
1: inventor
A preorder traversal visits the nodes in the tree in a top-down fashion: first
the root node is visited, then all of its child nodes are recursively visited.
`_.walk.postorder` does the opposite, calling the visitor function for a node
only after visiting all of its child nodes.
Collection Functions
——————–
The \_.walk module provides versions of most of the
[Underscore collection functions](http://underscorejs.org/#collections), with
some small differences that make them better suited for operating on trees. For
example, you can use `_.walk.filter` to get a list of all the strings in a tree:
_.walk.filter(_.walk.preorder, _.isString);
Like many other functions in _.walk, the argument to `filter` is a function
indicating in what order the nodes should be visited. Currently, only
`preorder` and `postorder` are supported.
Custom Walkers
————–
Sometimes, you have a tree structure that can’t be naively traversed. A good
example of this is a DOM tree: because each element has a reference to its
parent, a naive walk would encounter circular references. To handle such cases,
you can create a custom walker by invoking `_.walk` as a function, and passing
it a function which returns the descendants of a given node. E.g.:
var domWalker = _.walk(function(el) {
return el.children;
});
The resulting object has the same functions as `_.walk`, but parameterized
to use the custom walking behavior:
var buttons = domWalker.filter(_.walk.preorder, function(el) {
return el.tagName === ‘BUTTON’;
});
However, it’s not actually necessary to create custom walkers for DOM nodes —
_.walk handles DOM nodes specially by default.
Parse Trees
———–
A _parse tree_ is tree that represents the syntactic structure of a formal
language. For example, the arithmetic expression `1 + (4 + 2) * 7` might have the
following parse tree:
var tree = {
‘type’: ‘Addition’,
‘left’: { ‘type’: ‘Value’, ‘value’: 1 },
‘right’: {
‘type’: ‘Multiplication’,
‘left’: {
‘type’: ‘Addition’,
‘left’: { ‘type’: ‘Value’, ‘value’: 4 },
‘right’: { ‘type’: ‘Value’, ‘value’: 2 }
},
‘right’: { ‘type’: ‘Value’, ‘value’: 7 }
}
};
We can create a custom walker for this parse tree:
var parseTreeWalker = _.walk(function(node) {
return _.pick(node, ‘left’, ‘right’);
});
Using the `find` function, we could find the first occurrence of the addition
operator. It uses a pre-order traversal of the tree, so the following code
will produce the root node (`tree`):
parseTreeWalker.find(tree, function(node) {
return node.type === ‘Addition’;
});
We could use the `reduce` function to evaluate the arithmetic expression
represented by the tree. The following code will produce `43`:
parseTreeWalker.reduce(tree, function(memo, node) {
if (node.type === ‘Value’) return node.value;
if (node.type === ‘Addition’) return memo.left + memo.right;
if (node.type === ‘Multiplication’) return memo.left * memo.right;
});
When the visitor function is called on a node, the `memo` argument contains
the results of calling `reduce` on each of the node’s subtrees. To evaluate a
node, we just need to add or multiply the results of the left and right
subtrees of the node.