How to get union of several immutable.js Lists

Question

So, I have List a:

let a = Immutable.List([1])

and List b:

let b = Immutable.List([2, 3])

I want to get List union === List([1, 2, 3]) from them.

I try to merge them fist:

let union = a.merge(b); // List([2, 3])

It seems like merge method operates with indexes, not with values so overrides first item of List a with first item of List b. So, my question is what is the most simple way to get union of several lists (ideally without iterating over them and other extra operations).

Hirohito

Are you looking for a.concat(b)? – Aerobiosis

@Aerobiosis god dammed, don't notice it in the doc ) Thanks. can you paste that as an answer so that I can accept it. – Hirohito

Lmao, I also didn't see concat.. tried all kinds of things.. thanks :) – Cychosz

I think you need to look at Set data type. – Oleaginous

Answer 1

You are correct about merge. Merge will update the index with the current value of the merging list. So in your case you had

[0] = 1

and merged it with

[0] = 2
[1] = 3

which ended up overwriting [0]=1 with [0]=2, and then set [1]=3 resulting in your observed [2,3] array after merging.

A very simple approach to solving this would be to use concat

var a = Immutable.List([1]);
var b = Immutable.List([2,3]); 

var c = a.concat(b);

And it will work for this situation. However, if the situation is more complex, this may be incorrect. For example,

var a = Immutable.List([1,4]);
var b = Immutable.List([2,3,4]); 

this would give you two 4's which is not technically a union anymore. Unfortunately there is no union included in Immutable. An easy way to implemented it would be to set each value in each list as the key to an object, and then take those keys as the resulting union.

jsFiddle Demo

function union(left,right){
 //object to use for holding keys
 var union = {};

 //takes the first array and adds its values as keys to the union object
 left.forEach(function(x){
  union[x] = undefined;
 });

 //takes the second array and adds its values as keys to the union object
 right.forEach(function(x){
  union[x] = undefined;
 });

 //uses the keys of the union object in the constructor of List 
 //to return the same type we started with
 //parseInt is used in map to ensure the value type is retained
 //it would be string otherwise
 return Immutable.List(Object.keys(union).map(function(i){ 
  return parseInt(i,10); 
 }));
}

This process is O(2(n+m)). Any process which uses contains or indexOf is going to end up being O(n^2) so that is why the keys were used here.

late edit

Hyper-performant

function union(left,right){
    var list = [], screen = {};
    for(var i = 0; i < left.length; i++){
        if(!screen[left[i]])list.push(i);
        screen[left[i]] = 1;
    }
    for(var i = 0; i < right.length; i++){
        if(!screen[right[i]])list.push(i);
        screen[right[i]] = 1;
    }
    return Immutable.List(list);
}

Achromat

I believe this can be a problematic as a general approach - when the values are more complex. It'll work for values that are immutable types - Map for example - because the type's toString() method is implemented - but then it means that every time you add the value as an object key you end up calling toString() - which results in performance hit. – Auvil

@DoronZavelevsky - I disagree, as a general approach there is nothing wrong with this. In your specific micro-optimization of being concerned about using toString, I made a special version to avoid that case in the event others are also concerned. You can see it in the late edit section. – Achromat

Answer 2

Actually Immutable.js does have a union - it is for the Set data structure:

https://facebook.github.io/immutable-js/docs/#/Set/union

The great thing about Immutable.js is it helps introduce more functional programming constructs into JS - in this instance a common interface and the ability to abstract away data types. So in order to call union on your lists - convert them to sets, use union and then convert them back to lists:

var a = Immutable.List([1, 4]);
var b = Immutable.List([2, 3, 4]); 
a.toSet().union(b.toSet()).toList(); //if you call toArray() or toJS() on this it will return [1, 4, 2, 3] which would be union and avoid the problem mentioned in Travis J's answer.

Delta

Thanks for answering but I guess it is rather anti-pattern then pattern. Converting several lists to sets and then back seems to be overhead comparing with usage of built-in concat method. – Hirohito

I love how simple this answer is.. was surprised by how performant Travis J's answer is by comparison: jsperf.com/immutable-union/2 – Fibrin

Yeah you wouldn't want to do this often, and honestly, if using set operations it probably makes sense to use the set data structure. That said, I agree, functional programming constructs make for very elegant and simple solutions - I'd be curious to see the performance of this similar operation using mori.js over immutable (since it is a more performant library) – Delta

I tried the command and while works great, I do get duplication in values (in my case the lists are comprised of Class instances (objects), what's the best way to check and remove duplication on same key id of my object? Thanks, Sean. – Ikkela

A note: Set does not preserve the incoming order of items. Thats a big caveat. – Oleaginous

Answer 3

The implementation of List#merge has changed since this question was posted, and in the current version 4.0.0-rc-12 List#merge works as expected and solves the issue.

Fielder