遞迴的 lambdas

假設我們希望將 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 遞迴,沒有嚴重的限制或顯著的開銷。