"Invert" a JavaScript object hash whose values are arrays to produce a new object hash with keys as the elements of those original value vectors

Question

Background

lodash and underscore have an invert function that takes an object hash and converts it to a new one, which has keys as the input object's values and values as the input object's keys. As such, if the values in the input object aren't unique, this non-unique input value will, when it's a key in the output object, have as its value only one of the input object's keys.

An example:

_.invert({a: 1, b: 2, c: 2})
// { 1 : "a", 2 : "c" }

The twist

I frequently work with object hashes whose values are one-dimensional arrays (vectors). I've written a function using lodash/underscore (NB. only tested with lodash) that performs an array-aware invert, whose output object has keys that are the unique elements of the input object's value vectors, and values that are the input object's keys.

function arrayAwareInvert(obj) {
 return _.object(_.flatten(_.map(obj, function(valVec, key) {
 return valVec.map(function(val) { return [ val, key ]; });
 })));
}

I'd appreciate feedback on this function.

(NB. I can't use lodash/underscore's built-in invert with an object hash with array-valued keys because the resulting object has keys which simply stringify the arrays—an output object key might be [1, 2, 3].toString(), and entirely useless.)

Example use

Just to confirm that it works:

arrayAwareInvert({a: [1, 2], b: [3, 4]})
// { 1: "a", 2: "a", 3: "b", 4: "b" }

Per the original invert's behavior, if the elements of the input object's value vectors aren't unique (that is, if multiple value vectors contain the same element), the output object's value for those non-unique elements will be one of the input object keys:

arrayAwareInvert({a: [1, 2], b: [3, 4, 2]})
// { 1: "a", 2: "b", 3: "b", 4: "b" } // NB: 2: "b" here

Implementation notes

My implementation seems as brute-force as possible: it's effectively a doubly-nested loop, with the outer loop going over all input object keys and the inner loop going over the contents of each input object value (which is a vector).

A [key, value] tuple is built for each iteration of the inner-most loop, where "key"/"value" refer to the output object.

flatten is used to remove one level of nesting, i.e., transform [[[k1, v1]], [[k2, v2], [k3, v3]]] to [[k1, v1], [k2, v2], [k3, v3]].

Finally object is called to convert this list of 2-tuple key-value pairs into an object hash.

Summary

Are there implementations that occupy more advantageous positions in the clarity-speed-elegance phase space?

Does this operation have a more general name?

Analyses of solutions

reduce

I can simplify? @Flambino's solution a bit with _.merge:

function arrayAwareInvert(obj) {
 return _.reduce(obj, function (result, values, key) {
 return _.merge(result, 
 _.mapValues(_.object(values), function(v) { return key; }));
 }, {});
}

I like using merge here because it describes what's happening very well. But I don't really like how much code is needed to combine a vector and a string into an object hash with keys as elements of the vector and values as the string:

_.mapValues(_.object(values), function(v) { return key; })

As one (of many) alternatives, you could do this instead:

_.object(values, values.map(function(v) { return key; }))

but both of these seem obfuscated, compared with how clear the reduce and merge steps are.

• 200_success: Could you clarify why you tagged this question with both underscore.js and lodash.js?
• 200_success: Object keys in JavaScript are always stringified.
• Ahmed Fasih: @200_success I added a link to underscore's invert to attempt to answer your question. In more general terms, both libraries offer invert without a straightforward way to generalize them to array-valued objects, so I tagged them both. Since my implementation uses functions available in both, I feel this is ok.
• Ahmed Fasih: @200_success regarding stringified keys: edited to expand on why stringified arrays as keys is different than what I want, and what my function accomplishes.
• Flambino: Please don't update your question with new/different code, but feel free to ask a new question with the new code. Please see this meta post: What you may and may not do after receiving answers

Answer 1

lodash and underscore both have a reduce (aka "fold") function that works on objects, meaning you could also do this:

function arrayAwareInvert(obj) {
 return _.reduce(obj, function (result, values, key) {
 _.forEach(values, function (value) { result[value] = key; });
 return result;
 }, {});
}

It's pretty much the functional-style equivalent of Bergi's answer.

Point is, reduce is probably what you want for this.

---

Edit: As Bergi points out in the comments the inner iteration could also be a reduce operation

function arrayAwareInvert(obj) {
 return _.reduce(obj, function (result, values, key) {
 return _.reduce(values, function (result, value) {
 result[value] = key;
 return result;
 }, result);
 }, {});
}

• Bergi: Hm, forEach is not very functional-style. You'd rather nest two reduces.
• Ahmed Fasih: Ah, definitely reduce is the perfect thing for this situation. I was hoping there might be some fancy thing I could do with partial or curry but I'll take reduce. Agree with @Bergi about forEach but I will see if that can be replaced with merge.
• Flambino: @Bergi True, but I didn't want to overdo it. This keeps it closer to your solution, which straight-forward to grasp. Still, you're right, and I'll add the reduce-reduce solution
• Bergi: It's just I'd either do a for-for, foreach-foreach or reduce-reduce solution, but not mix them. Having two loops that essentially do the same written in different ways is confusing.
• Flambino: @Bergi Sure, I see what you mean. My rationale was partly the an inner reduce requires you to pass in the result even though it's already available as a closure, so that seemed a little unnecessary. Sure it's mixing things a little, but with the closure, the forEach really ends up doing the same thing as a reduce. Anyway, added a reduce-reduce solution

Answer 2

Your implementation is quite elegant, but it constructs a lot of intermediate objects so speed could be optimised by writing a more native version:

function arrayAwareInvert(obj) {
 var res = {};
 for (var p in obj) {
 var arr = obj[p], l = arr.length;
 for (var i=0; i<l; i++) {
 res[arr[i]] = p;
 }
 }
 return res;
}

Which of these is clearer would depend on the readers familiarity with functional programming and the underscore library.

• Flambino: +1 though you might consider adding a if(!ob.hasOwnProperty(p)) continue; line
• Bergi: @Flambino: It's a data object, not an instance, so it won't have inherited enumerable properties (from Object.prototype). No need for if (!Object.prototype.hasOwnProperty.call(obj, p)).
• Flambino: I'm not saying is necessary, but it might be a worthwhile precaution. Besides, lodash uses it, which means your code acts slightly different than the original code. Yes, edge case, but still
• Ahmed Fasih: You know, I wrote pretty much this when I needed a non-unique-value-entries version of arrayAwareInvert which output an object whose values were arrays, similar to invert with the optional second boolean as true.
• Bergi: Oops, because || binds stronger than =. It needs to be (... || (...=...))....