This is an attempt to do memoization without mutation. I've left comments in the code regarding how I'd prefer this to work.

gistfile1.js

var memoize = function(func){

    var cache = function(a) {
        return {
            get: function() {
                return a;
            },
            set: function(b) {
                return cache(a.concat(createArray([], b)));
            }
        };
    };

    var createArray = function(arr, n) {
        var build = function(newArray, count) {
            if (count < 1) {
                return newArray.concat(n);
            } else {
                return build(newArray.concat([,]), count - 1);
            }
        };
        return build(arr, n);
    };

  var result = function(c) {
        var begin = c ? c : cache([]);
        return function(arg) {
            var val = begin.get()[arg];
            if (val) {
                return arg + ' retrieved from cache';
            } else {
                return result(begin.set(func(arg)));
                // this works but if the arg is not in the cache a new function is
                // returned instead
                // I would like to return "arg + ' not in cache'" instead here and
                // find a way of still being able to update the cache whilst retaining
                // immutability
            }
        };
    };
    return result(false);
};


var memo = memoize(function(a) {
	return a;
});

var start = memo(5);
console.log(start(5)); // 5 retrieved from cache

// I'd prefer to do this with just two calls to memo rather than having to store the
// first call in a variable

First off, createArray can be shortened by using this little trick var a = Array.apply(null, Array(3));.

Secondly, when you want immutability someone has do deal with it. It's either your code or the client code. In your case if you want to keep memoize immutable you'll have to return the cache along with the result of the wrapped function for each call to memo. That's what you have right now although in a slightly different style. You're returning a function which closes over the cache instead instead of returning the result and the cache. This is the issue you're having troubles with. You want to return 2 things to the client code – the result of applying func and the new cache map – but you're only returning one thing: either the result when it's cached or a function when it's not cached.

If you really want to keep immutability then have the function produced by result return a 2-element array or maybe a 2-property map. One element is the result returned by func, the other is the updated cache. The same function would also have to take cache as an argument. It's not ideal but there's no magic way to get rid of it.

You can alleviate the burden on the user code by currying this function. Similar to what I did in my monads article, which describes the state monad, and this type of monad is exactly what a memoize utility needs.

I've adapted the code in my blog post to be used for memoization. https://gist.github.com/4597568#file-memoization-js-L30-L44. As you can see I'm constantly receiving and returning the cache along with the computed result. And the way I got rid of it was by currying and then building that sequence abstraction to hide the part that threads the state along.

Hopefully my explanation won't confuse you more.