Writing Universal memoization function in C++11

Question

Looking for a way to implement a universal generic memoization function which will take a function and return the memoized version of the same?

Looking for something like @memo (from Norving's site)decorator in python.

def memo(f):     table = {}     def fmemo(*args):         if args not in table:             table[args] = f(*args)         return table[args]     fmemo.memo = table     return fmemo 

Going more general, is there a way to express generic and reusable decorators in C++, possibly using the new features of C++11?

Answer 1

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;         }     }; } 

In C++14, one can use generalized return type deduction to avoid the extra indirection imposed by returning std::function.

Making this fully general, permitting passing arbitrary function objects without wrapping them in std::function first is left as an exercise for the reader.

Answer 2

The right way to do memoization in C++ is to mix the Y-combinator in.

Your base function needs a modification. Instead of calling itself directly, it takes a templateized reference to itself as its first argument (or, a std::function<Same_Signature> recursion as its first argument).

We start with a Y-combinator. Then we add in a cache on the operator() and rename it to memoizer, and give it a fixed signature (for the table).

The only thing left is to write a tuple_hash<template<class...>class Hash> that does a hash on a tuple.

The type of the function that can be memoized is (((Args...)->R), Args...) -> R, which makes the memoizer of type ( (((Args...) -> R), Args...) -> R ) -> ((Args...) -> R). Having a Y-combinator around to produce a 'traditional' recursive implementation can also be useful.

Note that if the function memoized modifies its args during a call, the memoizer will cache the results in the wrong spot.

struct wrap {};  template<class Sig, class F, template<class...>class Hash=std::hash> struct memoizer; template<class R, class...Args, class F, template<class...>class Hash> struct memoizer<R(Args...), F, Hash> {   using base_type = F; private:   F base;   mutable std::unordered_map< std::tuple<std::decay_t<Args>...>, R, tuple_hash<Hash> > cache; public:      template<class... Ts>   R operator()(Ts&&... ts) const   {     auto args = std::make_tuple(ts...);     auto it = cache.find( args );     if (it != cache.end())       return it->second;      auto&& retval = base(*this, std::forward<Ts>(ts)...);      cache.emplace( std::move(args), retval );      return decltype(retval)(retval);   }   template<class... Ts>   R operator()(Ts&&... ts)   {     auto args = std::tie(ts...);     auto it = cache.find( args );     if (it != cache.end())       return it->second;      auto&& retval = base(*this, std::forward<Ts>(ts)...);      cache.emplace( std::move(args), retval );      return decltype(retval)(retval);   }    memoizer(memoizer const&)=default;   memoizer(memoizer&&)=default;   memoizer& operator=(memoizer const&)=default;   memoizer& operator=(memoizer&&)=default;   memoizer() = delete;   template<typename L>   memoizer( wrap, L&& f ):     base( std::forward<L>(f) )   {} };  template<class Sig, class F> memoizer<Sig, std::decay_t<F>> memoize( F&& f ) { return {wrap{}, std::forward<F>(f)}; } 

live example with a hard-coded hash function based off this SO post.

auto fib = memoize<size_t(size_t)>(   [](auto&& fib, size_t i)->size_t{     if (i<=1) return 1;     return fib(i-1)+fib(i-2);   } );