js: List

gistfile1

var Empty = {
  contains:  function(x)     { return false; },
  incl:      function(x)     { return new NonEmpty(x, Empty, Empty); },
  union:     function(other) { return other; },
  toString:  function()      { return '.'; }
};

var NonEmpty = function(elem, left, right) {

  return {

    contains:  function(x) {
                  if(x < elem) { return left.contains(x); }
                  if(x > elem) { return right.contains(x); }
                  return true;
               },
    incl:      function(x) {
                  if(x < elem) { return new NonEmpty(elem, left.incl(x), right); }
                  if(x > elem) { return new NonEmpty(elem, left, right.incl(x)); }
                  return this;
               },
    union:     function(other) {
                  return ((left.union(right)).union(other)).incl(elem);
               },
    toString:  function() {
                  return '{' + left + elem + right + '}';
               }
  };

};

var List = function() {
  return (function build(xs, acc) {
  
    if(xs.length === 0) return acc;
    return build(Array.prototype.slice.call(xs, 1), acc.incl(xs[0]));

  })(Array.prototype.slice.call(arguments, 1), Empty.incl(arguments[0]));

};