Skip to content

Instantly share code, notes, and snippets.

@gerardpaapu
Created March 23, 2011 22:32
Show Gist options
  • Save gerardpaapu/884181 to your computer and use it in GitHub Desktop.
Save gerardpaapu/884181 to your computer and use it in GitHub Desktop.
Sets represented as javascript functions, with an Object Oriented(tm) interface
var Set = function (test) {
this.test = test;
};
Set.prototype = {
'add': function(s) {
return Set.add(this, s);
},
'complement': function () {
return Set.complement(this);
},
'union': function(s) {
return Set.union(this, s);
},
'remove': function(v) {
return Set.remove(this, v);
},
'intersection': function(s) {
return Set.intersection(this, s);
},
'exclusiveDisjunction': function(s) {
return Set.exclusiveDisjunction(this, s);
},
'subtract': function(s) {
return Set.subtract(this, s);
},
'contains': function(v) {
return Set.contains(this, v);
}
};
// Set ::== Set.empty()
// ::== Set.add(<Set>, v)
// ::== Set.remove(<Set>, v)
// ::== Set.complement(<Set>, v)
// ::== Set.union(<Set>, <Set>)
Set.empty = function () {
return new Set(function () { return false; });
};
Set.add = function (s, v1) {
return new Set(function (v2) {
return v2 === v1 || s.test(v2);
});
};
Set.complement = function(s) {
return new Set(function(v) {
return !s.test(v);
});
};
Set.union = function(s1, s2) {
return new Set(function (v) {
return s1(v) || s2(v);
});
};
// contains(s, v) -> boolean ; the membership test
// contains(empty(), _) -> false ; the empty Set contains no values
// contains(add(s, v), v) -> true ; add(s, v) always contains v
// contains(complement(s), v) = !contains(s, v) ;
// contains(union(s1, s2), v) = contains(s1, v) || contains(s2, v) ;
Set.contains = function(s, v) {
return s.test(v);
};
// contains(Set.remove(s, v), v) -> false ; Set.remove(s, v) never contains v
Set.remove = function(s, v) {
var s2 = Set.complement(Set.add(v, Set.empty()));
return Set.intersection(s, s2);
};
// intersection(s1, s2) -> a Set that contains only elements that are members of both s1 and s2
// !intersect = !(s1 & s2) = !a | !a
// intersect = !(!a | !a)
Set.intersection = function(s1, s2) {
return Set.complement(
Set.union(
Set.complement(s1),
Set.complement(s2)));
};
// subtract(s1, s2) -> a Set than contains all elements of s1 that are not members of s2
Set.subtract = function (s1, s2) {
return Set.intersection(Set.complement(s2), s1);
};
// exclusiveDisjunction(s1, s2) -> a Set that contains all members that are in either s1 or s2 but not both
Set.exclusiveDisjunction = function (s1, s2) {
return Set.intersection(
Set.complement(Set.intersection(s1, s2)),
Set.union(s1, s2));
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment