C++でラムダ式を再帰させる

ラムダ式を再帰させたい、そんな場面は少なからずあるだろう。
もちろんC++的にはループで処理したり、STLコンテナにブチ込んで for_each させたほうが性能は出るのかもしれないが、再帰処理によるコンパクトなコードは魅力である。
管理すべき変数が減るのも頭に優しい。
そういう意味で使い捨ての関数にも名前を付けたくない、ならばラムダだ。

しかし、はて、ラムダには名前がない。
呼ぶべき自分の名前が分からない。
いや、ラムダ式なので名前というよりかは自分の姿か。

結論から言うと、自分の名前は第三者に教えてもらえば良いのだ。
つまり、再起したいラムダ式に自分自身を受け取るための引数をひとつ追加し、別の関数にそのラムダを渡してイイ感じに実行してもらえばいい。

これを、不動点コンビネータという。

Wikipediaを調べると仰々しい記事が出てくるし、ググれば解説も沢山出てくるだろう。
自分のコードに数学的で高尚なアトモスフィアを持ち込むのにうってつけである。

なんか詳しい説明は調べたらいくらでも出てくるのでここはさっさと解法を示して終わる。

例題としてはみんな大好き階乗の計算を使う。
階乗をラムダ式で書こうとしたらこんな具合になるだろう。

呼ぶべき自分の名前が分からない。
そこでとりあえず、呼ぶべき関数を受け取れるようにちょいちょいと改造しておく。

呼ぶべき関数は第一引数で受け取るのがミソだ。
引数に型推論の補助が入っているのは再帰のせいで返り値型が分からなくなったからで、深く気にしなくてもいいだろう。

そしてこんな感じの道具を用意する。
もちろんコイツもラムダ式で書いているので別に変数としてバインドしておく必要はないが、コードがクソ長くなるのも嫌なので、名前を付けておこう。

こいつをYコンビネータという。
さっきの階乗は以下のような形でコイツにぶち込む。

そんでもって、Yコンビネータだと困るパターンがどうもあるらしい。
この辺りは完全に勉強不足なので正直、なんでおまえもっと詳しい記事がいくらでもあるのにまた記事を書いてるんだって話になるかもしれないけど、高尚な記事ばっかだったのでひとつくらいは意識の低そうな記事があってもいいんじゃないかと思った。
あとどれもこれも長すぎて読む気が失せるし。

とりあえず、なんか改善したらしいのがZコンビネータと呼ばれるもので、そのためにひとつ道具を作っておく。

カリー化という。
これも詳しい説明は腐るほどあるから説明はしないが、こいつはラムダ式の再帰意外にも色々使えて便利なヤツ。

そんでもって、本命のZコンビネータはこうなる。

使い方はYコンビネータと同じで、上のコードのYをZに書き換えるだけでおk。

ちなみにC++で不動点コンビネータを扱った記事は結構あるのだが、なぜかZコンビネータの定義にカリー化を使ったものが見当たらない。
俺が不勉強なだけでカリー化を使うと不都合なケースがあるのかもしれないが、実際に試して動いたし、見た目がちょっとマシになったのでこれもネットに放流しといたほうがいいだろうと思ってこういう記事を書いた。

実行効率は詳しいサイトがいくらでもあるのでわざわざ書かないが、十分速いらしいのでスタックオーバーフロー以外は心配しなくてもいい。

以下余談

ラムダ式は参照キャプチャよりコピーキャプチャしたほうが速いらしいので、この記事でもそうするように書いておいたが、実際使ってみた感想として、コピーされると困るような関数オブジェクトは結構多かったりする。
なので変数などにバインドしておくのではなく、ケースバイケースでその場にあったものを使い捨てるのが良いのかもしれない。
そういう意味で、変数としてラムダ式を保存するのではなくて、ちょっとづつ変えたパターンをそれぞれプリプロセッサマクロとして定義しておくのがベストかもしれない。
もしくはユニバーサル参照。

それと、ラムダ式はもちろん便利だが、なんにでも、例えば普通に関数として書けるものにも無闇矢鱈と使うのは正直やめたほうがいい。
コンパイルエラーが読めたものじゃなくなる。
名前がついていないとはそういうことだ。

使ってみて一番良かったのは、カリー化もYコンビネータもZコンビネータも、一番外側は constexpr な関数として定義しておいて、引数の関数はユニバーサル参照で受けるようにしたやつだった。