如何在C++中实现带记忆化的匿名递归Fix组合子？

要实现无需显式指定类型的MemoFix，核心是让编译器从lambda的签名中自动推导记忆化所需的参数类型(Arg)和返回类型(Ret)，而非手动指定模板参数。以下是修改后的实现：

#include <iostream>
#include <unordered_map>

// 用于解析lambda运算符签名的辅助模板
template<typename F>
struct lambda_traits;

// 特化处理lambda的const成员函数（大多数无mutable的lambda都是const）
template<typename F, typename Ret, typename Self, typename Arg>
struct lambda_traits<Ret (F::*)(Self, Arg) const> {
    using return_type = Ret;
    using arg_type = Arg;
};

template<typename F>
struct MemoFix {
    F f;
    // 从lambda的operator()中提取返回类型和参数类型
    using traits = lambda_traits<decltype(&F::operator())>;
    using Ret = typename traits::return_type;
    using Arg = typename traits::arg_type;
    
    std::unordered_map<Arg, Ret> cache{};

    Ret operator()(Arg x) {
        if (!cache.contains(x)) {
            cache[x] = f(std::ref(*this), x);
        }
        return cache[x];
    }
};

// 推导指南：让编译器从传入的lambda自动推导MemoFix的模板参数F
template<typename F>
MemoFix(F) -> MemoFix<F>;

int main() {
    // 现在可以直接用简洁的写法定义记忆化递归函数
    auto fact = MemoFix{[](auto self, int n) -> int {
        return (n <= 1) ? 1 : n * self(n - 1);
    }};

    std::cout << fact(5) << std::endl; // 输出120
}

修改说明 #

1. 移除冗余模板参数：
   原MemoFix的Ret和Arg模板参数被移除，改为通过lambda_traits从lambda的operator()签名中自动提取，避免手动重复指定类型。

2. lambda签名解析：
   lambda_traits模板特化用于解析lambda的const operator()成员函数类型，提取出递归函数的返回类型(return_type)和输入参数类型(arg_type)。

3. 自动推导指南：
   添加了模板推导指南MemoFix(F) -> MemoFix<F>，让编译器可以直接从传入的lambda推导出MemoFix的模板参数F，无需显式写出MemoFix<decltype(lambda), ...>。

4. 保持性能与简洁性：
   全程未使用std::function，避免了额外的性能开销；同时保留了原Fix类的匿名递归写法，无需为lambda额外命名。

扩展：支持多参数记忆化 #

如果需要支持多参数的递归函数，可以将参数打包为std::tuple，并为std::tuple提供哈希函数（C++20及以后标准库默认支持部分tuple的哈希，或自行实现）。修改后的示例：

#include <iostream>
#include <unordered_map>
#include <tuple>

// 扩展lambda_traits支持多参数
template<typename F>
struct lambda_traits;

template<typename F, typename Ret, typename Self, typename... Args>
struct lambda_traits<Ret (F::*)(Self, Args...) const> {
    using return_type = Ret;
    using args_tuple = std::tuple<Args...>;
};

template<typename F>
struct MemoFix {
    F f;
    using traits = lambda_traits<decltype(&F::operator())>;
    using Ret = typename traits::return_type;
    using ArgsTuple = typename traits::args_tuple;
    
    std::unordered_map<ArgsTuple, Ret> cache{};

    template<typename... Args>
    Ret operator()(Args&&... args) {
        ArgsTuple key{std::forward<Args>(args)...};
        if (!cache.contains(key)) {
            cache[key] = f(std::ref(*this), std::forward<Args>(args)...);
        }
        return cache[key];
    }
};

template<typename F>
MemoFix(F) -> MemoFix<F>;

// 示例：计算二维动态规划问题（比如网格路径数）
int main() {
    auto grid_path = MemoFix{[](auto self, int m, int n) -> int {
        if (m == 1 || n == 1) return 1;
        return self(m-1, n) + self(m, n-1);
    }};

    std::cout << grid_path(3, 3) << std::endl; // 输出6
}

这样就可以支持任意多参数的记忆化递归函数，同时保持简洁的写法。

内容的提问来源于stack exchange，提问作者Harumaki