Implementations of immutable object oriented sets from William Cook's essay "On Understanding Data Abstraction, Revisited" (http://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf). Set.rb is idiomatic Ruby, set.js is sort of idiomatic JavaScript, and set2.js is less idiomatic, but more faithful to the paper.

set.js

/*
 * Idiomatic-ish JavaScript. Constructor functions use the `new`
 * keyword, but we don't use prototype objects.
 */

function Empty () {
    this.isEmpty = true;
    this.contains = function (i) { return false; };
    this.insert = function (i) { return new Insert(this, i); };
    this.union = function (s) { return s; };
};

function Insert (s, n) {
    this.isEmpty = false;
    this.contains = function (i) { return n == i || s.contains(i); };
    this.insert = function (i) { return new Insert(this, i); };
    this.union = function (s) { return new Union(this, s); };
};

function Union (s1, s2) {
    this.isEmpty = false;
    this.contains = function (i) { return s1.contains(i) || s2.contains(i); };
    this.insert = function (i) { return new Insert(this, i); };
    this.union = function (s) { return new Union(this, s); };
};

set.rb

class Empty
  def empty?
    true
  end

  def contains?(i)
    false
  end

  def insert(i)
    Insert.new(self, i)
  end

  def union(s)
    s
  end
end

class Insert
  def initialize(s, n)
    @s = s
    @n = n
  end

  def empty?
    false
  end

  def contains?(i)
    @n == i || @s.contains?(i)
  end

  def insert(i)
    Insert.new(self, i)
  end

  def union(other)
    Union.new(self, other)
  end
end

class Union
  def initialize(s1, s2)
    @s1 = s1
    @s2 = s2
  end

  def empty?
    false
  end

  def contains?(i)
    @s1.contains?(i) || @s2.contains?(i)
  end

  def insert(i)
    Insert.new(self, i)
  end

  def union(other)
    Union.new(self, other)
  end
end

set2.js

/*
 * Not as idiomatic JavaScript. Constructor functions expect
 * to be called without the new keyword: s1 = Empty();
 */

function Empty () {
    var self = {
        isEmpty: true,
        contains: function (i) { return false; },
        insert: function (i) { return Insert(self, i); },
        union: function (s) { return s; },
    };

    return self;
};

function Insert (s, n) {
    if (s.contains(n)) {
        return s;
    } else {
        var self = {
            isEmpty: false,
            contains: function (i) { return n == i || s.contains(i); },
            insert: function (i) { return Insert(self, i); },
            union: function (s) { return Union(self, s); },
        };
    
        return self;
    }
};

function Union (s1, s2) {
    var self = {
        isEmpty: false,
        contains: function (i) { return s1.contains(i) || s2.contains(i); },
        insert: function (i) { return Insert(self, i); },
        union: function (s) { return Union(self, s); },
    };

    return self;
};