Semigroup List comparisons.js

/*
So, let's play with some Semigroups and (maybe?) Monoids for combining lists in interesting ways
*/

//This one is pretty straightforward
//Union (keep all values from both lists, but no repeats)
const Union = function(xs){
  if (!(this instanceof Union)) {
    return new Union(xs);
  }
  this.xs = xs;
}

Union.of = xs => Union(xs);

//exploit ES6 sets
Union.prototype.concat = function({xs:ys}) {
  return Union(
    [...(new Set(this.xs.concat(ys)))]
  )
};
Union.prototype.fold = function(f=(x=>x)) {
  return f(this.xs);
};


Union.empty = Union.prototype.empty = () => Union([]);
//Union.zero = Union.prototype.zero = //???? I think this would 
//hypothetically be a list of all possible values but let's not try...

//Intersection: the concat should keep any values that appear in BOTH lists
const Intersection = function(xs){
  if (!(this instanceof Intersection)) {
    return new Intersection(xs);
  }
  this.xs = xs;
}

Intersection.of = xs => Intersection(xs);

Intersection.prototype.concat = function({xs}) {
  return Intersection(
    this.xs.filter(
      x=>xs.some(y=>x===y)
    )
  )
};
Intersection.prototype.fold = function(f=(x=>x)) {
  return f(this.xs);
};

//here's the tricky bit: not sure empty is straightforwardly possible to have an mempty that fits intuition in all ways
//Intersection([]), for instance, fails monoid laws
//Intersection.empty = Intersection.prototype.empty = ??? would also have to be a list containing _all_ possible elements, I think!
Intersection.zero = Intersection.prototype.zero = () => Intersection([]);


//that means any foldMap-ish thing we use HAS to avoid using mempty to work as expected, 
//and also make sure that the first element is mapped along with the rest

//anyhow... the next one is a "difference" of lists, and here things get way weirder for me.  
//First we'll need a quick utility to just get the non-symetrical difference of two lists
function difference(first, second) {
  var out = [];
  var idx = 0;
  var firstLen = first.length;
  while (idx < firstLen) {
    if (!second.includes(first[idx]) && !out.includes(first[idx])) {
      out[out.length] = first[idx];
    }
    idx += 1;
  }
  return out;
}



//and now we can think about a _symmetric_ Difference semigroup as
//Difference: any values which are NOT in "both" lists
//something about "in both" here worries me...

const Difference = function(xs){
  if (!(this instanceof Difference)) {
    return new Difference(xs);
  }
  this.xs = xs;
}

Difference.of = xs => Difference(xs);

Difference.prototype.concat = function({xs}) {
  return Difference(
    difference(this.xs, xs).concat(difference(xs, this.xs))
  )
};
Difference.prototype.fold = function(f=(x=>x)) {
  return f(this.xs);
};


Difference.empty = Difference.prototype.empty = () => Difference([]);
//seems straightforward, but then...

/*
Difference([3,4]).concat(Difference([4,5]));//-> [3,5]
Difference([3,4])
  .concat(Difference([4,5]))
  .concat(Difference([4,5]));//-> [3,4] but wait, 4 is in EVERY list in this operation!

What's happening is that the first concat op rejects the 4 as "in both", but then there's no 4 left 
in the next operation... so it's "not in both" again.  This actually seems to all work out per the associativity 
law, but it's confusing as heck if you want to think of "unique elements" when foldMapping. 
That's clearly NOT what this does/gets in a larger context...
  */

//so maybe we could create a semigroup with a sense of its "history"? Ruling out what it's "seen" so far?
const DifferenceH = function(xs,out){
  if (!(this instanceof DifferenceH)) {
    return new DifferenceH(xs, out);
  }
  this.xs = xs;
  this.out = out;
}

DifferenceH.of = xs => DifferenceH(xs, []);

//almost certainly more efficient ways to do this but this should be right...
DifferenceH.prototype.concat = function({xs,out}) {
  return DifferenceH(
    this.xs.filter(
      x=>!xs.concat(out).includes(x)
    )
    .concat(
      xs.filter(
        x=>!this.xs.concat(this.out).includes(x)
      )
    ),
    Intersection(this.xs)
      .concat(Intersection(xs))
      .fold(x=>x)
      .concat(out)//add in previous outs as well...
      .concat(this.out)
  )
};
DifferenceH.prototype.fold = function(f=(x=>x)) {
  return f(this.xs);//here we're losing the history on purpose
};

DifferenceH.empty = DifferenceH.prototype.empty = () => DifferenceH([],[]);

//And guess what, it actually seems to work/fit intuition!
//foldMap(DifferenceH, DifferenceH.of, [[1,2],[3,4],[1,5],[5,4]]);//-> DH[xs:[2,3],out:[4,5,1]]

//of course, it also feels odd in another way: outside of its use in a foldMap, how/why would a 
//random type floating around ever have a "history" outside of the context of a larger operation?
//Like, DifferenceH.of([1,2]) vs. DifferenceH([1,2],[3,4])
//weird stuff, an probably some bigger patterns I'm missing

//one other thing this DifferenceH doesn't do, that one might imagine it would, is Union the elements in a given array
//That is, the same element CAN appear twice in one of the component arrays and still be counted in the list of uniques
//as if it were "unique" at the end: in fact it will _continue_ to appear in the final array: twice!
//_should_ it appear twice? Depends on the definition of what difference implies.  Maybe it _should_ only appear once
//or maybe it should not appear at all, since it appeared "twice"!
//this makes sense to some extent, though it can be "fixed" to have these other behaviors as well, albiet at even greater complexity cost