There is an interesting way to do it that does rely neither on rebinding nor the behavior of def. The main trick is to go around the limitations of recursion by passing a function as an argument to itself: (defn make-fibo [y] (let [fib (fn [mem-fib x] (let [fib (fn [a] (mem-fib mem-fib a))] (if … Read more
This library is a straightforward combinatorization of the well-known technique of memoization. Let’s start with the canonical example: fib = (map fib’ [0..] !!) where fib’ 0 = 0 fib’ 1 = 1 fib’ n = fib (n-1) + fib (n-2) I interpret what you said to mean that you know how and why this … Read more
How about this? First write a one-argument memoizer: static Func<A, R> Memoize<A, R>(this Func<A, R> f) { var d = new Dictionary<A, R>(); return a=> { R r; if (!d.TryGetValue(a, out r)) { r = f(a); d.Add(a, r); } return r; }; } Straightforward. Now write a function tuplifier: static Func<Tuple<A, B>, R> Tuplify<A, B, … Read more
You can’t do what you want using lru_cache, since it doesn’t provide an API to access the cache, and it might be rewritten in C in future releases. If you really want to save the cache you have to use a different solution that gives you access to the cache. It’s simple enough to write … Read more
You could take a Map as cache and take nested maps for all following arguments. This cache works for arbitrary count of arguments and reuses the values from the former calls. It works by taking a curried function and an optional Map. If the map is not supplied, a new map is created which serves … Read more
Here is the commit (and subsequent discussion) where Memoizable was deprecated: https://github.com/rails/rails/commit/36253916b0b788d6ded56669d37c96ed05c92c5c The author advocates the @foo ||= … approach and points to this commit as an example for migration: https://github.com/rails/rails/commit/f2c0fb32c0dce7f8da0ce446e2d2f0cba5fd44b3. Edit: Note that I don’t necessarily interpret this change as meaning that all instances of memoize can or should be replaced w/ this pattern. … Read more
I found a better way to memoize using Scala: def memoize[I, O](f: I => O): I => O = new mutable.HashMap[I, O]() { override def apply(key: I) = getOrElseUpdate(key, f(key)) } Now you can write fibonacci as follows: lazy val fib: Int => BigInt = memoize { case 0 => 0 case 1 => 1 … Read more
Python offers a very elegant way to do this – decorators. Basically, a decorator is a function that wraps another function to provide additional functionality without changing the function source code. Your decorator can be written like this: import json def persist_to_file(file_name): def decorator(original_func): try: cache = json.load(open(file_name, ‘r’)) except (IOError, ValueError): cache = {} … Read more
A compact one returning a lambda: template <typename R, typename… Args> std::function<R (Args…)> memo(R (*fn)(Args…)) { std::map<std::tuple<Args…>, R> table; return [fn, table](Args… args) mutable -> R { auto argt = std::make_tuple(args…); auto memoized = table.find(argt); if(memoized == table.end()) { auto result = fn(args…); table[argt] = result; return result; } else { return memoized->second; } }; … Read more
Consider calculating the fibonacci sequence: Pure recursion: int fib(int x) { if (x < 2) return 1; return fib(x-1) + fib(x-2); } results in exponential number of calls. Recursion with memoization/DP: int fib(int x) { static vector<int> cache(N, -1); int& result = cache[x]; if (result == -1) { if (x < 2) result = 1; … Read more