ラムダ式の再帰でautoを使った場合の簡潔な書き方はあるのか？

Question

この質問はC++14での話です。C++17からはこうなるみたいな情報もあれば嬉しいです。

###概要

C++14からラムダ式の仮引数にもautoが使えるようになりましたが、このautoを使ったときにラムダ式の再帰を簡潔に書く方法がわかりません。

###サンプルコード
下記コードはコラッツの問題において、何ステップで1になるかを数える処理です(負の値の場合とか細かいエラー処理とかは省いています)。

#include <functional>
#include <iostream>

// C++11 での書き方
int collatz_count1(int x)
{
	std::function<int(int)> f = [&f](int n) {
		if (n == 1) {
			return 0;
		} else if (n % 2 == 0) {
			return f(n / 2) + 1;
		} else {
			return f(3 * n + 1) + 1;
		}
	};
	return f(x);
}

// C++14 でのみ動作
int collatz_count2(int x)
{
	auto f = [](auto g, auto n) {
		if (n == 1) {
			return 0;
		} else if (n % 2 == 0) {
			return g(g, n / 2) + 1;
		} else {
			return g(g, 3 * n + 1) + 1;
		}
	};
	return f(f, x);
}

// コンパイルエラー
int collatz_count3(int x)
{
	auto f = [&f](auto n) {
		if (n == 1) {
			return 0;
		} else if (n % 2 == 0) {
			return f(n / 2) + 1;
		} else {
			return f(3 * n + 1) + 1;
		}
	};
	return f(x);
}

// コンパイルエラー
int collatz_count4(int x)
{
	auto f = [&f](int n) {
		if (n == 1) {
			return 0;
		} else if (n % 2 == 0) {
			return f(n / 2) + 1;
		} else {
			return f(3 * n + 1) + 1;
		}
	};
	return f(x);
}

int main()
{
	int i = 27;
	std::cout << "collatz_count1: " << collatz_count1(i) << std::endl;
	std::cout << "collatz_count2: " << collatz_count2(i) << std::endl;
	std::cout << "collatz_count3: " << collatz_count3(i) << std::endl;
	std::cout << "collatz_count4: " << collatz_count4(i) << std::endl;
	return 0;
}

collatz_count1とcollatz_count2はうまく動きます(collatz_count1はC++11でも)が、collatz_count3 とcollatz_count4はコンパイルエラーになります。fの型をdecltype(auto)にコンパイルエラーになります。

###何が問題なのか？
もっと汎用的にするため、ラムダ式の仮引数を(auto n)のようにした場合、collatz_count1のような書き方はできなくなると思っています。なぜならstd::function<int(int)>みたいな型をどのようにも書けないからです(かといってstd::function<int(int)>と書いてしまうと、せっかくのautoがintに確定してしまいます)。となると上のcollatz_count3 のような書き方で動いて欲しいのですが、fの型が確定していないためキャプチャできないとエラーになります。これはcollatz_count4も同じで、同じエラーとなります。そこで、collatz_count2のように、キャプチャではなく引数で渡せばうまく動きますが、簡潔とは言い難いです。

つまり、何がしたいかというと、

• ラムダ式の仮引数の型はautoにしてテンプレートのように使いたい。
• しかし、その場合の再帰はキャプチャでは実現できなくなるのをなんとかしたい。

なんとか方法はないのでしょうか？それとも現在のC++14の仕様ではcollatz_count2のように書くしかないのでしょうか？

###検証環境
OS: macOS 10.12.1
GCC: Homebrew gcc 6.2.0
Clang: Apple LLVM version 8.0.0 (clang-800.0.42.1)

-std=c++14付きでコンパイルしています。

###参考文献
C++ : ラムダ式のみでの再帰文 - Qiita
C++プログラマ キャスブログ
ラムダ式で再帰関数 - C++と色々
c++ - Recursive lambda functions in C++11 - Stack Overflow

Answer 1

ラムダ式の自己再帰呼出しには、Recursive lambda functions in C++14 回答のように不動点コンビネータを介する方法があります。

→ 追記：書いた後に気づいたのですが本質的にはcollatz_count2と等価ですね。

template<typename Functor>
struct fix_type {
    Functor functor;

    template<typename... Args>
    decltype(auto) operator()(Args&&... args) const&
    { return functor(functor, std::forward<Args>(args)...); }
};

template<typename Functor>
fix_type<typename std::decay<Functor>::type> fix(Functor&& functor)
{ return { std::forward<Functor>(functor) }; }

int collatz_count5(int x)
{
    auto f = fix([](auto&& f, int n) {
        if (n == 1) {
            return 0;
        } else if (n % 2 == 0) {
            return f(f, n / 2) + 1;
        } else {
            return f(f, 3 * n + 1) + 1;
        }
    });
    return f(x);
}

（個人的にはラムダ式の"名前"が欲しいなら普通の関数でいいじゃない派なので、ネタとロマンの追求以外ではこのようなコーディングには賛同しませんが）

C++17からはこうなるみたいな情報もあれば嬉しいです。

C++1z(17)でのラムダ式まわりの言語拡張は *thisコピーキャプチャ と constexprラムダ ですから、本件に関しては実装の選択肢が増えたりしないと思います。私見ですが、autoによる静的型推論とC++の静的型システムの上で実現する以上、collatz_count2/collatz_count5以外の実装手段は将来的にもでてこないのではと思います。

Answer 2

こんにちは。

近しい話題がnamed lambdaが必要な理由にありました。

autoは使えない。なぜなら、autoの名前は、その初期化式の中では、使えないからだ。

だそうです。
そして、named lamdaを使えばできるとか。N2511で提案されてます。規格に入る見込みは分かりませんが。

Comments

[raccy]

named lambdaっすか。なんかJavaScriptを思い出してしましたが、これ欲しいですね。

[Chironian]

そうですね。最早「無名関数」と呼べなくなるのが残念（？）かも。

うはっ、今、N2511でぐぐったら、この質問が最初のページに出てきましたよ。
グーグルなんて仕事が速いんだ！！

[raccy]

named lambdaが規格に入ることを期待して…ベストアンサーに！
(ベストアンサーにしても、規格に入るかは無関係なんですけどねー)

[Chironian]

あは。ありがとう。