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

Question

I would like to visit a "recursive" std::variant using lambdas and overload-creating functions (e.g. boost::hana::overload).

---

Let's assume I have a variant type called my_variant which can store one an int, a float or a 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;
};

(I'm using a wrapper my_variant_wrapper class in order to define the variant type recursively.)

---

I want to recursively visit the variant printing different things depending on the stored types. Here's a working example using a struct-based visitor:

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

Calling std::visit with the above visitor prints the desired output:

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
*/ 

---

I would like to locally create the visitor as a series of overloaded lambdas using boost::hana::overload and boost::hana::fix.

fix is an implementation of the Y-combinator, which can be used to implement recursion in type-deduced lambdas. (See this question for more information.)

This is what I tried, and expected to work:

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

My reasoning is as follows:

• boost::hana::fix returns an unary generic lambda that can be used as the visitor for an std::variant.

• boost::hana::fix takes a binary generic lambda where the first parameter is an unary function that allows recursion of the lambda, and the second parameter is the initial argument for the body of the lambda.

• Calling boost::hana::overload with handlers for all the possible types inside my_variant creates some sort of visitor which is equivalent to struct_visitor.

• Using self instead of lambda_visitor inside the const std::vector<my_variant_wrapper>& overload should allow recursion to work properly.

• Immediately calling the created overload with bh::overload(...)(x) should trigger the recursive visitation.

Unfortunately, as you can see in this wandbox example, the lambda_visitor example fails to compile, spewing out a lot of almost-undecipherable template-heavy errors:

...

/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)...); }

...

---

The error seems similar to what I would get without using 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);

---

What am I doing wrong? Is it possible to achieve local recursive variant visitation using fix, overload and a set of lambdas?

My intuition was that lambda_visitor would have been "equivalent" to struct_visitor, thanks to the indirection offered by fix.

Answer 1

Let's pick a simpler example. We want to implement gcd using the fix-point combinator. First go might be something like:

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

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

This fails to compile with gcc ultimately producing this error:

/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)...); }
                                                  ^

The lambda we're passing to fix() has a deduced return type. But how do we deduce it? There's only a single return statement, and that one is recursive! We need to give the compiler some help. Either we need to break apart our return statement so that one has a clear type:

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

or simply provide the return type explicitly:

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

Both of these options compile and work.

The same is true of your original example. If you just specify that the lambda returns void, everything works:

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