Typescript - Finding matching keys and paths in a multidimensional object

Update

I clearly was cutting and pasting some code from elsewhere when I originally wrote this, as I included two functions that weren't being used at all. They're removed now.

I also added below an explanation of how I might, step-by-step, convert one of these functions from an ES5 style to the modern JS version in the answer. I believe ES6+ is a major improvement, and I like the function as I wrote it much better, but for those learning modern JS, such an explanation might be useful.

The updated original answer follows and then these transformation steps.

It's really unclear to me what you're looking for. My best guess is that you want to accept an array of objects like the above and return a function that takes a value like "circle" or "()" and returns the path to that value on one of those objects, namely ['two', 'three']. But that guess could be way off.

Here's a version that does this based on a few reusable functions:

// Helpers
const path = (ps = [], obj = {}) =>
  ps .reduce ((o, p) => (o || {}) [p], obj)

const findLeafPaths = (o, path = [[]]) => 
  typeof o == 'object'
    ? Object .entries (o) .flatMap (
        ([k, v]) => findLeafPaths (v, path).map(p => [k, ...p])
      ) 
    : path


// Main function
const makeSearcher = (xs) => {
  const structure = xs .reduce (
    (a, x) => findLeafPaths (x) .reduce ((a, p) => ({...a, [path (p, x)]: p}), a),
    {}
  )
  return (val) => structure[val] || [] // something else? or throw error?
}


// Demonstration
const objs = [
  {one: "square", two: {three: "circle", four: {five: "triangle"}}}, 
  {one: "[]", two: {three: "()", four: {five: "/\\"}}}
]

const searcher = makeSearcher(objs)

console .log (searcher ('()'))        //~> ['two', 'three']
console .log (searcher ('circle'))    //~> ['two', 'three']
console .log (searcher ('triangle'))  //~> ['two', four', 'five']
console .log (searcher ('[]'))        //~> ['one']
console .log (searcher ('heptagon'))  //~> []
        

We start with two helper functions, path, and findLeafPaths. These are all reusable functions. The first borrows its API from Ramda, although this is a separate implementation:

• path accepts a list of nodes (e.g. ['two', 'three']) and an object and returns the value at that path if all the nodes along the way exist

• findLeafPaths takes an object and viewing it as a tree, returns the paths of all leaf nodes. Thus for your first object, it would return [['one'], ['two', 'three'], ['two', 'four', 'five']]. Again we ignore arrays, and I'm not even sure what we would need to do to support them.

The main function is makeSearcher. It takes an array of objects like this:

[
  {one: "square", two: {three: "circle", four: {five: "triangle"}}}, 
  {one: "[]", two: {three: "()", four: {five: "/\\"}}}
]

and converts it them into a structure that looks like this:

{
  'square'   : ['one']
  'circle'   : ['two', 'three']
  'triangle' : ['two', 'four', 'five']
  '[]'       : ['one']
  '()'       : ['two', 'three']
  '/\\'      : ['two', 'four', 'five']
}

and then returns a function that simply looks up the values from this structure.

I have some vague suspicions that this code is not quite as well thought-out as I like, since I can't find a better name for the helper object than "structure". Any suggestions would be welcome.

Transforming ES5 to modern JS

Here we show a series of transformations from ES5 to modern Javascript code. Note that I actually wrote these in the other order, as the ES6+ is now what come naturally to me after working in it for a few years. This may be helpful for those coming from ES5 backgrounds, though.

We're going to convert a version of findLeafPaths. Here is a version that I think skips all ES6+ features:

const findLeafPaths = function (o, path) {
  if (typeof o == 'object') {
    const keys = Object .keys (o)
    const entries = keys .map (key => [key, o [key]])
    const partialPaths = entries .map ( function ([k, v]) {
      const paths = findLeafPaths (v, path || [[]])
      return paths .map (function(p) {
        return [k].concat(p)
      })
    })
    return partialPaths.reduce(function(a, b) {
      return a.concat(b)
    }, [])
  }
  return path || [[]]
}

The first thing we do is use Object.entries to replace the dance with getting the object's keys and then mapping those to get the [key, value] pairs:

const findLeafPaths = function (o, path) {
  if (typeof o == 'object') {
    const entries = Object .entries (o)
    const partialPaths = entries .map (function ([k, v]) {
      const paths = findLeafPaths (v, path || [[]])
      return paths .map (function(p) {
        return [k] .concat (p)
      })
    })
    return partialPaths.reduce(function (a, b) {
      return a .concat (b)
    }, [])
  }
  return path || [[]]
}

Next, the pattern of mapping, then flattening by reducing with concatenation has a a built-in Array method, flatMap. We can simplify by using that:

const findLeafPaths = function (o, path) {
  if (typeof o == 'object') {
    const entries = Object .entries (o)
    return entries .flatMap (function ([k, v]) {
      const paths = findLeafPaths (v, path || [[]])
      return paths .map (function(p) {
        return [k] .concat (p)
      })
    })
  }
  return path || [[]]
}

Now we can tweak this to take advantage of the modern spread syntax in place of concat:

const findLeafPaths = function (o, path) {
  if (typeof o == 'object') {
    const entries = Object .entries (o)
    return entries .flatMap ( function ([k, v]) {
      const paths = findLeafPaths (v, path || [[]])
      return paths .map (function(p) {
        return [k, ...p]
      })
    })
  }
  return path || [[]]
}

Arrow functions will simplify things further. Here we replace the innermost function call with an arrow:

const findLeafPaths = function (o, path) {
  if (typeof o == 'object') {
    const entries = Object .entries (o)
    return entries .flatMap ( function ([k, v]) {
      const paths = findLeafPaths (v, path || [[]])
      return paths .map (p => [k, ...p])
    })
  }
  return path || [[]]
}

We're repeating that path || [[]] expression in two places. We could use a default parameter to only have one:

const findLeafPaths = function (o, path = [[]]) {
  if (typeof o == 'object') {
    const entries = Object .entries (o)
    return entries .flatMap ( function ([k, v]) {
      return findLeafPaths (v, path) .map (p => [k, ...p])
    })
  }
  return path
}

Now we replace the next function expression (supplied to entries.flatmap()) with an arrow:

const findLeafPaths = function (o, path = [[]]) {
  if (typeof o == 'object') {
    const entries = Object .entries (o)
    return entries .flatMap (
      ([k, v]) => findLeafPaths (v, path) .map (p => [k, ...p])
    )
  }
  return path
}

entries is a temporary variable that we use only once in the line after it's defined. We can remove it easily:

const findLeafPaths = function (o, path = [[]]) {
  if (typeof o == 'object') {
    return Object .entries (o) .flatMap (
      ([k, v]) => findLeafPaths (v, path) .map (p => [k, ...p])
    )
  }
  return path
}

From a functional perspective, working with expressions is preferable to working with statements. They are more susceptible to analysis and they don't depend on external ordering. Hence, I will choose a conditional expression ("ternary statement") to an if-else one. So I prefer this version:

const findLeafPaths = function (o, path = [[]]) {
  return typeof o == 'object'
    ? Object .entries (o) .flatMap (
        ([k, v]) => findLeafPaths (v, path) .map (p => [k, ...p])
      ) 
    : path
}

Finally, we can replace the outermost function expression with another arrow function to get the version in the answer above:

const findLeafPaths = (o, path = [[]]) => 
  typeof o == 'object'
    ? Object .entries (o) .flatMap (
        ([k, v]) => findLeafPaths (v, path) .map (p => [k, ...p])
      ) 
    : path

Obviously we could do the same sort of thing with path and makeSearcher as well.

Note that every step of this reduced the line or character count of the function. That is nice, but it is not at all the most important point. More relevant is that each version is arguably simpler than the one preceding it. This does not mean that it's more familiar, only that fewer ideas are being twined together. (Rich Hickey's Simple Made Easy talk does a great idea of explaining the difference between these often-confused notions.)

I work often with junior developers, and getting them through this transition is important to the growth of their skills. There were no difficult steps in there, but the end result is substantially simpler than the original. After some time, writing directly in this style can become second-nature.