Tree generation with a monoidal reduction

Over the past couple of months, we have looked at map, filter, and reduce along with monoids. Today, we'll take a look at a problem from the Syracuse, New York JavaScript meetup that involves some of what we have covered so far.

Let's say we have a list of Guess Who characters with their attributes that looks like this:

[
  {
    "name": "Alex",
    "hairColor": "Black",
    "wearingHat": false,
    "wearingGlasses": false
  },
  ...
]

And we want to organize them into a decision tree that looks like this:

{
  "hairColor: Black": {
    "wearingGlasses: true": {
      "wearingHat: true": [],
      "wearingHat: false": []
    },
    "wearingGlasses: false": {
      "wearingHat: true": [],
      "wearingHat: false": []
    }
  },
  ...
}

How would you go about solving this problem? We could iterate over each attribute nested within each other and find all characters that match that combination of attributes as we go. This could work, but what if we added another attribute or wanted to change the order of the nesting?

Let's imagine we have an array of attributes that defines the order of the nesting for our tree. Instead of iterating over the attributes, we could iterate over the characters and place each one where it belongs in the tree. We could create the tree ahead of time and simply place the characters in the branch they belong in, but we're going to create the branches as we go instead.

Path generation using map

First we need to generate the path so we can reference its location in the tree. For example, the character Alex has black hair and is not wearing glasses or a hat, so he would be placed in the tree at location tree["hairColor: Black"]["wearingGlasses: false"]["wearingHat: false"]. So given a character and list of attributes, we can generate this path using the map method:

const key = (attribute) => 
  `${attribute}: ${character[attribute]}`;
const path = attributes.map(key);

Creating a branch from the path

Now that we have the path, we can create a branch and place the character in that newly created branch. To accomplish this, we can reduce over the path, returning the reference to the inner object as we go. Objects and arrays are always passed by reference in JavaScript. If we are at the end of the path, we'll add the item to the list instead of creating a nested object. After appending the entire path to the branch, we need to return the whole thing back.

const createBranch = (path, item) => {
  const branch = {};
  path.reduce((branch, key, i) => {
    const endOfPath = i == path.length - 1;
    branch[key] = endOfPath ? [item] : {};
    return branch[key];
  }, branch);
  return branch;
};

Deep merging the tree

Finally, we can build the tree as we go by deeply merging all the branches we create as we go. I'm using the excellent deepmerge library to do exactly that. Deep merge is a function that takes two objects and returns a new object with the properties combined (with the second overriding the first if there are conflicts). If we merge any object with an empty object, we'll end up with the object we started with. This means that deep merging objects is a monoid, and it plays nicely with reduce. Let's see the whole thing in action:

const deepmerge = require("deepmerge");

const createBranch = (path, item) => {
  const branch = {};
  path.reduce((branch, key, i) => {
    const endOfPath = i == path.length - 1;
    branch[key] = endOfPath ? [item] : {};
    return branch[key];
  }, branch);
  return branch;
};

const attributes = ["hairColor", "wearingGlasses", "wearingHat"];
const decisionTree = guessWhoCharacters
  .reduce((tree, character) => {
    const key = (attribute) => 
      `${attribute}: ${character[attribute]}`;
    const path = attributes.map(key);
    const branch = createBranch(path, character.name);
    return deepmerge(tree, branch);
  }, {});

And that's it! We only iterate over each character once. Additionally, if we added any attributes or wanted to change the order of the tree nesting, all we would have to do is update the attributes array. A previous solution for this problem that I came up with avoided creating new branches if they already existed, but with a bit of added complexity. I like the simplicity and readability of this solution.

If you have a different solution that you'd like to share, please put it in the comments! Next time, we'll take a deeper dive into functors.