Cannot resist. Must add memoization.

objectunion.js

// Boilerplate
function objectUnion(definer) {
    var defined = 0, length = 0, isDefined = false, definitions, key;

    definitions = definer(function() {
        var names = arguments, fold;
        if(isDefined) {
            throw new TypeError('This objectUnion has already been defined');
        }
        function wrapped(args) {
            if(!(this instanceof wrapped)) {
                args = Array.prototype.slice.call(arguments);
                args.isArguments = true;
                return new wrapped(args);
            }
            args = args.isArguments ? args : arguments;
            if(args.length != names.length) {
                throw new TypeError("Expected " + names.length + " arguments, got " + args.length);
            }
            for(i = 0; i < names.length; i++) {
                this[names[i]] = args[i];
            }
        }
        wrapped.prototype.fold = (function(index) {
            return function() {
                var args = [], i;
                if(arguments.length != defined) {
                    throw new TypeError("Expected " + defined + " arguments, got " + arguments.length);
                }
                for(i = 0; i < names.length; i++) {
                    args.push(this[names[i]]);
                }
                return arguments[index].apply(this, args);
            };
        })(defined);
        defined++;
        return wrapped;
    });

    for(key in definitions) {
        length++;
    }

    if(length != defined) {
        throw new Error("objectUnion's define function was called without result being returned");
    }

    isDefined = true;
    return definitions;
}

// AST
var AST = objectUnion(function(define) {
    return {
        Let: define('name', 'left', 'right'),
        StrLit: define('value'),
        NumLit: define('value'),
        BoolLit: define('value'),
        UndefinedLit: define()
    };
});

function astToString(ast) {
    return ast.fold(
        function(name, left, right) {
            return name + ' := ' + astToString(left) + ' ' + astToString(right);
        },
        function(value) {
            return JSON.stringify(value);
        },
        function(value) {
            return value;
        },
        function(value) {
            return value;
        },
        function() {
            return 'undefined';
        }
    );
}

console.log(astToString(AST.Let('brian', AST.StrLit('Brian McKenna'), AST.NumLit(22))));

// List
var List = objectUnion(function(define) {
    return {
        Cons: define('car', 'cdr'),
        Nil: define()
    };
});

function listToArray(list) {
    return list.fold(
        function(car, cdr) {
            return [car].concat(listToArray(cdr));
        },
        function() {
            return [];
        }
    );
}

console.log(listToArray(List.Cons(1, List.Cons(2, List.Nil()))));
// [0, 1]

// Stream
var Stream = objectUnion(function(define) {
    return {
        Cons: define('car', 'cdr'),
        Nil: define()
    };
});

function fibonacci(a, b) {
    function inner() {
        var memoized = false, shell, c;
        return function(a, b) {
            if (memoized) return shell;
            else {
                memoized = true;
                c = a + b;
                return shell = Stream.Cons(c, function() {
                    return inner()(b, c);
                });
            }
        };
    }

    return Stream.Cons(a, function() {
        return Stream.Cons(b, function() {
            return inner()(a, b);
        });
    });
}

function streamToArray(stream, limit) {
    if(!limit) return [];

    return stream.fold(
        function(car, cdr) {
            return [car].concat(streamToArray(cdr(), limit - 1));
        },
        function() {
            return [];
        }
    );
}

console.log(streamToArray(fibonacci(0, 1), 20));
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181 ]