使用 lambda 和定点组合器递归访问 std::variant

Question

我想访问 "recursive" std::variant 使用 lambda 和重载创建函数 （例如 boost::hana::overload )。

假设我有一个名为 my_variant 的变体类型，它可以存储一个 int、float 或 vector<my_variant>:

struct my_variant_wrapper;

using my_variant = 
    std::variant<int, float, std::vector<my_variant_wrapper>>;

struct my_variant_wrapper 
{
    my_variant _v;
};

（我正在使用包装器 my_variant_wrapper class 以递归定义变体类型。）

我想根据存储的类型递归访问打印不同内容的变体。这是一个 working example 使用基于 struct 的访问者：

struct struct_visitor
{
    void operator()(int x) const { std::cout << x << "i\n"; }
    void operator()(float x) const { std::cout << x << "f\n"; }

    void operator()(const std::vector<my_variant_wrapper>& x) const 
    { 
        for(const auto& y : x) std::visit(*this, y._v); 
    }
};

用上述访问者调用 std::visit 打印所需的输出：

my_variant v{
    std::vector<my_variant_wrapper>{
        my_variant_wrapper{45}, 
        std::vector<my_variant_wrapper>{
            my_variant_wrapper{1}, my_variant_wrapper{2}
        },
        my_variant_wrapper{33.f}
    }
};

std::visit(struct_visitor{}, v);

// Prints: 
/*
    45i
    1i
    2i
    33f
*/

我想使用 boost::hana::overload and boost::hana::fix 在本地将访问者创建为一系列重载的 lambda。

fix 是 Y-combinator, which can be used to implement recursion in type-deduced lambdas. (See 的实现以获取更多信息。）

这是我尝试过的，预计会奏效：

namespace bh = boost::hana;
auto lambda_visitor = bh::fix([](auto self, const auto& x)
    {
        bh::overload(
            [](int y){ std::cout << y << "i\n"; },
            [](float y){ std::cout << y << "f\n"; },
            [&self](const std::vector<my_variant_wrapper>& y)
            {
                for(const auto& z : y) std::visit(self, z._v);  
            })(x);
    });

我的推理如下：

boost::hana::fix returns 一个一元泛型 lambda，可用作 std::variant.
boost::hana::fix 采用二进制泛型 lambda，其中第一个参数是允许 lambda 递归的一元函数，第二个参数是 lambda 主体的初始参数。
使用 my_variant 中所有可能类型的处理程序调用 boost::hana::overload 会创建某种等同于 struct_visitor 的访问者。
在 const std::vector<my_variant_wrapper>& 重载中使用 self 而不是 lambda_visitor 应该允许递归正常工作。
立即使用 bh::overload(...)(x) 调用创建的重载应该触发递归访问。

不幸的是，as you can see in this wandbox example，lambda_visitor 示例无法编译，喷出大量几乎无法辨认的模板错误：

...

/usr/local/boost-1.61.0/include/boost/hana/functional/fix.hpp:74:50: error: use of 'main():: [with auto:2 = boost::hana::fix_t >; auto:3 = int]' before deduction of 'auto' { return f(fix(f), static_cast(x)...); }

...

该错误似乎与我在不使用 boost::hana::fix:

时得到的错误相似

auto lambda_visitor = bh::overload(
    [](int y){ std::cout << y << "i\n"; },
    [](float y){ std::cout << y << "f\n"; },
    [](const std::vector<my_variant_wrapper>& y)
    {
        for(const auto& z : y) std::visit(lambda_visitor, z._v);  
    });

std::visit(lambda_visitor, v);

error: use of 'lambda_visitor' before deduction of 'auto' for(const auto& z : y) std::visit(lambda_visitor, z._v);

我做错了什么？是否可以使用 fix、overload 和一组 lambda 来实现本地 递归变量访问 ？

我的直觉是 lambda_visitor 应该是 "equivalent" 到 struct_visitor，多亏了 fix 提供的间接寻址.

Answer 1

让我们选择一个更简单的例子。我们想使用定点组合器来实现 gcd 。第一次去可能是这样的：

auto gcd = bh::fix([](auto self, int a, int b) {
    return b == 0 ? a : self(b, a%b);
});

std::cout << gcd(12, 18);

使用 gcc 编译失败最终产生此错误：

/usr/local/boost-1.61.0/include/boost/hana/functional/fix.hpp:74:50: error: use of 'main()::<lambda(auto:2, int, int)> [with auto:2 = boost::hana::fix_t<main()::<lambda(auto:2, int, int)> >]' before deduction of 'auto'
         { return f(fix(f), static_cast<X&&>(x)...); }
                                                  ^

我们传递给 fix() 的 lambda 具有推导的 return 类型。但是我们如何推断呢？只有一个 return 语句，而且是递归的！我们需要给编译器一些帮助。要么我们需要分解我们的 return 语句，以便有一个清晰的类型：

auto gcd = bh::fix([](auto self, int a, int b) {
    if (b == 0) {
        return a;
    }
    else {
        return self(b, a%b);
    }
});

或者简单地明确提供 return 类型：

auto gcd = bh::fix([](auto self, int a, int b) -> int {
    return b == 0 ? a : self(b, a%b);
});

这两个选项都可以编译和工作。

你原来的例子也是如此。如果您只指定 lambda returns void，一切正常：

auto lambda_visitor = bh::fix([](auto self, const auto& x) -> void
//                                                        ^^^^^^^^
    {
        bh::overload(
            [](int y){ std::cout << y << "i\n"; },
            [](float y){ std::cout << y << "f\n"; },
            [&self](const std::vector<my_variant_wrapper>& y)
            {
                for(const auto& z : y) std::visit(self, z._v);  
            })(x);
    });

std::visit(lambda_visitor, v);

使用 lambda 和定点组合器递归访问 std::variant

Recursively visiting an `std::variant` using lambdas and fixed-point combinators

c++

lambda

variant

c++17

boost-hana