Рекурсивные лямбды. Кейсы
#опытным

Сегодня разберем пару кейсов, в которых можно использовать рекурсивные лямбды.

1️⃣ Начнем с очевидного. Где рекурсия, там всегда ошиваются какие-то древовидные структуры. Рекурсивные лямбды могут помочь сделать простые и не очень DFS обходы деревьев.

Можно обходить literaly деревья:

struct Leaf { };
struct Node;
using Tree = std::variant<Leaf, Node*>;
struct Node {
  Tree left;
  Tree right;
};

template<typename ... Lambdas>
struct Visitor : Lambdas...
{
  Visitor(Lambdas... lambdas) : Lambdas(std::forward<Lambdas>(lambdas))...
  {}
  using Lambdas::operator()...;
};

int main()
{
  Leaf l1;
  Leaf l2;
  Node nd{l1, l2};
  Tree tree = &nd;
  int num_leaves = std::visit(Visitor(
      [](Leaf const&) { return 1; },
      [](this const auto& self, Node* n) -> int {
        return std::visit(self, n->left) + std::visit(self, n->right);
      }
    ), tree);
}

Наше дерево хранит вариант ноды и листа. И мы можем с помощью паттерна overload обойти все веточки и посчитать листочки.

У вас может возникнуть вопрос: а как мы рекурсивно проходим все варианты лямбдой, которой предназначена только для нод?

Все дело в магии явного this. Здесь мы с вами говорили, что при наследовании и вызове метода базового класса this вывыводится в тип класса наследника. А наш визитор как раз является наследником лямбды, которая обходит ноды дерева. Таким образом мы рекурсивно используем весь визитор.

Можно таким же образом попробовать обходить какие-нибудь джейсоны и другие подобные структуры.

2️⃣ С помощью рекурсивных лямбд можно обходить compile-time структруры, типа туплов(даже вложенных):

auto printTuple = [](const auto& tuple) constexpr {
  auto impl = []<size_t idx>(this const auto& self, const auto& t) constexpr {
    if constexpr (idx < std::tuple_size_v<std::decay_t<decltype(t)>>) {
      std::cout << std::get<idx>(t) << " ";
      self.template operator()<idx+1>(t); // Рекурсивный вызов
    }
  };
  impl.template operator()<0>(tuple);
};

std::tuple<int, double, std::string> tp{1, 2.0, "qwe"};
printTuple(tp);

// Output:
// 1 2 qwe

Тут нам придется использовать шаблонные лямбды с индексом текущего элемента тупла в качества шаблонного параметра. Обратите внимание, как вызываются лямбды в данном случае. Так как у нас шаблонный оператор(), то компилятору надо явно сказать, что мы вызываем шаблон и также явно передать в него шаблонный параметр. Подобные лямбды с явным вызовом шаблонного оператора() желательно оборачивать в еще одну лямбду, чтобы коллеги случайно кофеем не подавились, увидев эту кракозябру.


3️⃣ Обход вложенных директорий с помощью std::filesystem:

auto listFiles = [](const std::filesystem::path& dir) {
    std::vector<std::string> files;
    auto traverse = [&](this const auto& self, const auto& path) {
        for (const auto& entry : std::filesystem::directory_iterator(path)) {
            if (entry.is_directory()) {
                self(entry.path());
            } else {
                files.push_back(entry.path().string());
            }
        }
    };
    traverse(dir);
    return files;
};

Ну тут вроде без пояснений все плюс-минус понятно.

Вообще, в любом месте, где применима небольшая по объему кода рекурсия, вы можете использовать рекурсивные лямбды.

Пишите в комменты, если в вас есть что добавить по юзкейсам. Если кто использует какие-то генеративные алгоритмы, для реализации которых подойдет рекурсивная лямбда, тоже пишите. В общем, пишите любые мысли по теме)

Be useful. Stay cool.

#cppcore #cpp23 #template