CODEWITHSUNDEEP
c++lambdavariantc++17boost-hana
Vittorio Romeo
Vittorio Romeo

Reputation: 93324

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

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:

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.

Upvotes: 10

Views: 2380

Answers (1)

Barry
Barry

Reputation: 303347

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

Upvotes: 10

Related Questions