Ordered set data structure in JavaScript from Functional Program Design in Scala course by Martin Odersky.

OrderedSet.js

function NonEmpty(elem, left, right) {

    const contains = (x) => {
        if (x < elem)
            return left.contains(x);
        else if (x > elem)
            return right.contains(x);
        else if (x === elem)
            return true;
        else
            throw new Error("Type mismatch");
    };

    const incl = (x) => {
        if (x < elem)
            return NonEmpty(elem, left.incl(x), right);
        else if (x > elem)
            return NonEmpty(elem, left, right.incl(x));
        else if (x === elem)
            return NonEmpty(elem, left, right);
        else
            throw new Error("Type mismatch");
    };

    const union = (other) => left.union(right.union(other)).incl(elem);

    const toString = () => {
        return "(" + left + " <- " + elem + " -> " + right + ")";
    };

    const size = () => 1 + left.size() + right.size();

    const toArray = () => [...left.toArray(), elem, ...right.toArray()];

    return Object.freeze({
        toArray,
        size,
        contains,
        incl,
        union,
        toString,
        valueOf: toString,
    });
}

function Empty() {
    const contains = (x) => false;
    const incl = (x) => NonEmpty(x, Empty(), Empty());
    const union = (other) => other;
    const toString = () => "Empty";
    const size = () => 0;
    const toArray = () => [];
    return Object.freeze({
        toArray,
        size,
        contains,
        incl,
        union,
        toString,
        valueOf: toString,
    });
}

function OrderedSet() {
    if(arguments.length > 0)
        return NonEmpty.apply(null, arguments);
    else
        return Empty();
}

// Some testing

function print() {
    const xs = [...arguments];
    console.log(...xs.map(String));
}

const xs = [23772, 11512, 30699, 31552, 25500, 12025, 6860, 26078, 28311, 32684, 32684];
const set = xs.reduce((set, x) => set.incl(x), OrderedSet());

print("Size should be 10:", set.size());
print(set);

const set1 = [13921, 10221, 19551, 31998, 7855].reduce((set, x) => set.incl(x), OrderedSet());
print("Size should be 5:", set1.size());
print(set1);

const set2 = set.union(set1);
print("New size 15:", set2.size());
print(set2);

const xs1 = set2.toArray();
print(xs1.length);
print(xs1);

// make it large
const set3 = Array(1000000).fill(0).map(() => Math.floor(Math.random() * 1000000)).reduce((set, x) => set.incl(x), OrderedSet());
print(set3.size());