遞迴的 lambdas

Created: November-22, 2018

假設我們希望將 Euclid 的 gcd() 寫為 lambda。作為一個功能，它是：

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}

但是 lambda 不能遞迴，它無法呼叫自身。lambda 沒有名稱，並且在 lambda 的主體內使用 this 指的是捕獲的 this（假設 lambda 是在成員函式的主體中建立的，否則它是一個錯誤）。那麼我們如何解決這個問題呢？

使用 `std::function`

我們可以讓 lambda 捕獲對尚未構建的 std::function 的引用：

std::function<int(int, int)> gcd = [&](int a, int b){
    return b == 0 ? a : gcd(b, a%b);
};

這有效，但應謹慎使用。它很慢（我們現在使用型別擦除而不是直接函式呼叫），它很脆弱（複製 gcd 或返回 gcd 會因為 lambda 引用原始物件而中斷），並且它不適用於通用 lambdas。

使用兩個智慧指標：

auto gcd_self = std::make_shared<std::unique_ptr< std::function<int(int, int)> >>();
*gcd_self = std::make_unique<std::function<int(int, int)>>(
  [gcd_self](int a, int b){
    return b == 0 ? a : (**gcd_self)(b, a%b);
  };
};

這增加了很多間接（這是開銷），但可以複製/返回，並且所有副本共享狀態。它確實讓你返回 lambda，否則不如上面的解決方案脆弱。

使用 Y 組合器

藉助簡短的實用程式結構，我們可以解決所有這些問題：

template <class F>
struct y_combinator {
    F f; // the lambda will be stored here

    // a forwarding operator():
    template <class... Args>
    decltype(auto) operator()(Args&&... args) const {
        // we pass ourselves to f, then the arguments.
        // the lambda should take the first argument as `auto&& recurse` or similar.
        return f(*this, std::forward<Args>(args)...);
    }
};
// helper function that deduces the type of the lambda:
template <class F>
y_combinator<std::decay_t<F>> make_y_combinator(F&& f) {
    return {std::forward<F>(f)};
}
// (Be aware that in C++17 we can do better than a `make_` function)

我們可以實現我們的 gcd：

auto gcd = make_y_combinator(
  [](auto&& gcd, int a, int b){
    return b == 0 ? a : gcd(b, a%b);
  }
);

y_combinator 是 lambda 演算中的一個概念，它允許你在定義之前無法命名自己的遞迴。這正是 lambda 所具有的問題。

你建立一個 lambda，將 recurse 作為其第一個引數。當你想要遞迴時，你傳遞引數 recurse。

然後 y_combinator 返回一個函式物件，該函式物件使用其引數呼叫該函式，但使用合適的 recurse 物件（即 y_combinator 本身）作為其第一個引數。它將你稱之為 y_combinator 的其餘引數轉發給 lambda。

簡而言之：

auto foo = make_y_combinator( [&](auto&& recurse, some arguments) {
  // write body that processes some arguments
  // when you want to recurse, call recurse(some other arguments)
});

你有一個 lambda 遞迴，沒有嚴重的限制或顯著的開銷。

使用 std::function

使用兩個智慧指標：

使用 Y 組合器

使用 `std::function`