Visiting Variants Using Lambdas – Part 2

In a previous article, “Visiting Variants Using Lambdas – Part 1,” we explored a technique leveraging boost::hana to perform variant visitation using lambdas without defining a class or struct. This article extends that approach, covering recursive variants and advanced visitation techniques.

Revisiting Basic Variant Visitation

The technique previously discussed involved boost::hana::overload, which allowed us to create a local visitor for a variant.

Example:

using vnum = vr::variant<int, float, double>;

auto vnp = make_visitor(
    [](int x)    { cout << x << "i\n"; },
    [](float x)  { cout << x << "f\n"; },
    [](double x) { cout << x << "d\n"; }
);

vnum v0{0};
vr::visit(vnp, v0); // Prints "0i"

v0 = 5.f;
vr::visit(vnp, v0); // Prints "5f"

v0 = 33.51;
vr::visit(vnp, v0); // Prints "33.51d"

Handling Recursive Variants

A recursive variant refers to a variant that can contain itself, making it useful for representing recursive data structures like JSON objects. However, since neither std::variant nor boost::variant use dynamic memory allocation, they have a fixed size, which prevents direct recursion.

Indirect Recursive Variants

To enable recursive variants, we introduce indirection via std::unique_ptr or std::vector.

Example:

struct my_variant {
    vr::variant<int, std::unique_ptr<my_variant>> _data;
};

Implementing Recursive vnum

To allow vnum to contain itself, we forward-declare a vnum_wrapper class:

namespace impl {
    struct vnum_wrapper;

    using varr = std::vector<vnum_wrapper>;
    using vnum = vr::variant<int, float, double, varr>;

    struct vnum_wrapper {
        vnum _data;

        template <typename... Ts>
        vnum_wrapper(Ts&&... xs) : _data{std::forward<Ts>(xs)...} {}
    };
}

using vnum = impl::vnum;
using impl::varr;

Now, vnum supports recursion:

vnum v0 = 0;
vnum v1 = 5.f;
vnum v2 = 33.51;
vnum v3 = varr{vnum{1}, vnum{2.0}, vnum{3.f}};
vnum v4 = varr{vnum{5}, varr{vnum{7}, vnum{8.0}, vnum{9.}}, vnum{4.f}};

Recursive Visitation

Traditional Recursive Visitation

A traditional approach involves defining a struct for visitation:

struct vnum_printer {
    void operator()(int x)    { cout << x << "i\n"; }
    void operator()(float x)  { cout << x << "f\n"; }
    void operator()(double x) { cout << x << "d\n"; }
    void operator()(const varr& arr) {
        for (const auto& x : arr) {
            vr::visit_recursively(*this, x);
        }
    }
};

A helper function simplifies recursive visitation:

template <typename TVisitor, typename TVariant>
decay_t<decltype(auto)> visit_recursively(TVisitor&& visitor, TVariant&& variant) {
    return vr::visit(
        std::forward<TVisitor>(visitor),
        std::forward<TVariant>(variant)._data
    );
}

Lambda-Based Recursive Visitation

Applying boost::hana::overload to recursive variants initially fails due to a self-referencing variable in initialization.

A workaround involves using the Y Combinator, implemented via boost::hana::fix, which allows lambda recursion without explicit function names.

Example:

auto factorial = boost::hana::fix([](auto self, auto n) -> int {
    return n == 0 ? 1 : n * self(n - 1);
});
assert(factorial(5) == 120);

Using this, we define make_recursive_visitor:

template <typename TReturn, typename... TFs>
auto make_recursive_visitor(TFs&&... fs) {
    return boost::hana::fix([&fs...](auto self, auto&& x) -> TReturn {
        return boost::hana::overload(std::forward<TFs>(fs)...)(
            [&self](auto&& v) { return vr::visit_recursively(self, v); },
            std::forward<decltype(x)>(x)
        );
    });
}

Using make_recursive_visitor

auto vnp = make_recursive_visitor<void>(
    [](auto, int x)    { cout << x << "i\n"; },
    [](auto, float x)  { cout << x << "f\n"; },
    [](auto, double x) { cout << x << "d\n"; },
    [](auto recurse, const varr& arr) {
        for (const auto& x : arr) recurse(x);
    }
);

Performance Comparison: std::function vs Y Combinator

Using std::function for recursive lambdas introduces overhead compared to boost::hana::fix.

Benchmark Results (Generated Assembly Size)

Compiler	Optimization	hana::fix	std::function	Overhead
g++	-O3	1583 bytes	4572 bytes	+189%
clang++	-O3	765 bytes	7146 bytes	+834%

Using boost::hana::fix significantly reduces code size compared to std::function.

Conclusion

This article explored recursive variants and how to visit them using lambdas. The Y Combinator approach provides a performant alternative to std::function, making it ideal for zero-overhead recursion in modern C++.