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
We can do this very efficiently by making a structure that we can index in sub-linear time. But first, {-# LANGUAGE BangPatterns #-} import Data.Function (fix) Let’s define f, but make it use ‘open recursion’ rather than call itself directly. f :: (Int -> Int) -> Int -> Int f mf 0 = 0 f … Read more
Relevant article on Programming.Guide: Dynamic programming vs memoization vs tabulation What is difference between memoization and dynamic programming? Memoization is a term describing an optimization technique where you cache previously computed results, and return the cached result when the same computation is needed again. Dynamic programming is a technique for solving problems of recursive nature, … Read more
GHC does not memoize functions. It does, however, compute any given expression in the code at most once per time that its surrounding lambda-expression is entered, or at most once ever if it is at top level. Determining where the lambda-expressions are can be a little tricky when you use syntactic sugar like in your … Read more
The evaluation mechanism in Haskell is by-need: when a value is needed, it is calculated, and kept ready in case it is asked for again. If we define some list, xs=[0..] and later ask for its 100th element, xs!!99, the 100th slot in the list gets “fleshed out”, holding the number 99 now, ready for … Read more
rev4: A very eloquent comment by user Sammaron has noted that, perhaps, this answer previously confused top-down and bottom-up. While originally this answer (rev3) and other answers said that “bottom-up is memoization” (“assume the subproblems”), it may be the inverse (that is, “top-down” may be “assume the subproblems” and “bottom-up” may be “compose the subproblems”). … Read more
Starting from Python 3.2 there is a built-in decorator: @functools.lru_cache(maxsize=100, typed=False) Decorator to wrap a function with a memoizing callable that saves up to the maxsize most recent calls. It can save time when an expensive or I/O bound function is periodically called with the same arguments. Example of an LRU cache for computing Fibonacci … Read more
OK, I will describe first the simplest solution which is O(N^2), where N is the size of the collection. There also exists a O(N log N) solution, which I will describe also. Look here for it at the section Efficient algorithms. I will assume the indices of the array are from 0 to N – … Read more
Memoization effectively refers to remembering (“memoization” → “memorandum” → to be remembered) results of method calls based on the method inputs and then returning the remembered result rather than computing the result again. You can think of it as a cache for method results. For further details, see page 387 for the definition in Introduction … Read more