Examples for _.walk

The _.walk module (underscore.collections.walk.js) provides implementations of the Underscore collection functions 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. For example, take a simple tree:

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, 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.