Created
January 16, 2013 21:19
-
-
Save stephendeyoung/4551065 to your computer and use it in GitHub Desktop.
This is an attempt to do memoization without mutation. I've left comments in the code regarding how I'd prefer this to work.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
First off,
createArray
can be shortened by using this little trickvar 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 tomemo
. 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 applyingfunc
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 byfunc
, the other is the updated cache. The same function would also have to takecache
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.