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

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);
}