使用 lambda 和“修复函数”快速记忆匿名递归函数

Question

背景

我最近了解到，定点组合器可以轻松定义递归函数而无需命名它们。 它主要用于函数式编程语言（例如

fix

function），但您可以在 C++20 中模仿它的外观，如下所示：

#include <iostream>

template <typename F>
struct Fix {
    F f;
    decltype(auto) operator()(auto arg) {
        return f(std::ref(*this), arg);
    }
};

int main() {
    auto fact = Fix{[](auto self, int n) -> int {
        return (n <= 1) ? 1 : n * self(n - 1);
    }};

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

您需要做的就是接收

auto self

作为 lambda 表达式的第一个参数来实现匿名递归。

我喜欢这种语法，因为它简单且通用。

问题

是否可以将函数式编程语言中使用的“修复函数”功能与记忆功能结合到 C++ 中的单个类中，例如

MemoFix

类，以便编写简洁的记忆递归函数？

详情

在编程比赛中，我经常想编写记忆函数。

因此，我开始创建一个包含

MemoFix

类的简单库，该类为“修复功能”添加了记忆功能。它将生成递归函数，同时使其成为记忆函数。

我已经写完了代码。但不幸的是，编译失败了。

#include <iostream>
#include <unordered_map>

template <typename F, typename Ret, typename Arg>
struct MemoFix {
    F f;
    std::unordered_map<Arg, Ret> cache{};

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

int main() {
    // not works, saying like "No viable constructor or deduction guide for deduction"
    auto fact = MemoFix{[](auto self, int n) -> int {
        return (n <= 1) ? 1 : n * self(n - 1);
    }};

    // works, but too redundant. I don't want to write `decltype`, types, and lambda names
    // auto body = [](auto self, int n) -> int {
    //     return (n <= 1) ? 1 : n * self(n - 1);
    // };
    // auto fact = MemoFix<decltype(body), int, int>{body};

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

unordered_set

用于记住返回值。 由于

unordered_set

需要显式类型参数，因此附加类型参数

Ret

和

Arg

均已标注。

只有通过指定模板参数（如

MemoFix<decltype(body), int, int>

）才能正确识别它们的类型。一旦你忽略了这一点，它就会立即出错。

我应该对

MemoFix

进行哪些更改才能允许编译器正确推断类型？

其他注意事项：

• 在 Clang 18.0、C++20（或更高版本）中
• 我不愿意使用

  std::function

  ，因为它存在性能缺陷。

如何使用最简单的符号进行记忆递归，而无需一遍又一遍地编写类型或为 lambda 表达式提供额外的名称？如果你有从另一个角度来看的方法，那也很好。我很高兴收到了解更多的人的建议。

Answer 1

我制作了

LambdaTraits

的简化版本，旨在提取参数类型和返回类型。

template <typename...> struct LambdaTraits;

template <typename F>
struct LambdaTraits<F> : public LambdaTraits<decltype(&F::operator())> {};

template<typename F, typename ...TArgs>
struct LambdaTraits<F, TArgs...> : LambdaTraits<decltype(&F::template operator()<TArgs...>)> {};

template <typename C, typename Ret, typename... Args>
struct LambdaTraits<Ret(C::*)(Args...) const> {
    using args_type = std::tuple<Args...>;
    using return_type = Ret;
};

struct Any {
    // template <typename T>
    // constexpr operator T&() const;

    template <typename T>
    T operator()(T) const;
};

template <typename F>
struct MemoFix {
    F f;
    using Arg = std::tuple_element_t<1, typename LambdaTraits<F, Any>::args_type>;
    using Ret = LambdaTraits<F, Any>::return_type;
    std::unordered_map<Arg, Ret> cache{};
};

演示