a cache-combinator inspired by y-combinator for use in competitive programming

template.cpp

/*
Example usage:
  int32_t main() {
    cout << 
      std::cache_combinator([](auto self, int n) -> int {
        if (n <= 2) return 1;
        return self(n - 1) + self(n - 2);
      })(50); // the 50-th fib number
  }
*/


namespace std {
  /// CACHE-COMBINATOR (made with love and deepseek on the 8th of may 2025)
  template <class Fun>
  class cached_combinator_result {
    Fun fun_;
  public:
    template <class T> explicit cached_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}
    template <class... Args> decltype(auto) operator()(Args &&...args) {
      // Define the key as a tuple of decayed arguments
      using KeyType = std::tuple<std::decay_t<Args>...>;
      KeyType key(args...);

      // Deduce the return type of the function when called with these arguments
      using ReturnType = std::invoke_result_t<Fun&, cached_combinator_result&, Args...>;

      // Static cache to persist across calls (shared per template instantiation)
      static std::map<KeyType, ReturnType> cache;

      auto it = cache.find(key);
      if (it != cache.end()) {
        return it->second;
      }

      // Compute the result and store it in the cache
      ReturnType result = fun_(*this, std::forward<Args>(args)...);
      cache.emplace(std::move(key), result);
      return result;
    }
  };

  template <class Fun> decltype(auto) cache_combinator(Fun &&fun) {
    return cached_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
  }


  /// Y-COMBINATOR (taken from https://usaco.guide/general/lambda-funcs?lang=cpp)
  template <class Fun> class y_combinator_result {
    Fun fun_;
  public:
    template <class T> explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}
    template <class... Args> decltype(auto) operator()(Args &&...args) {
      return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
  };

  template <class Fun> decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
  }

} // namespace std