C Sharpens you up

http://qiita.com/yuba に移しつつあります

C#, Java8のラムダで再帰関数を書く

.NET Java アルゴリズム

C#はラムダ記法で無名関数が書けますし、Javaも8からラムダ記法が可能になりました。

しかし無名関数では再帰関数が書けません。
さてどういうことか。

再帰関数の代表選手として階乗計算を例にとってみましょう。
まず、メソッドとして再帰的に書いてみます。

int Pow(int n) {
  return (n > 1) ? n * Pow(n - 1) : 1;
}

こうですね。では、これをラムダ記法で書こうとすると…

Func<int, int> pow
  = n => (n > 1) ? n * 【ここに書くメソッド名がない！】(n - 1) : 1;

そう、自分自身を呼ぼうにも自分自身は無名だから呼びようがないのです。困りました。

Javascriptを使う人は「arguments.calleeを使えばいい」と思うかもしれませんが、Javascriptだってもうarguments.calleeは非推奨ですからね。

さて、無名ゆえに自分自身を呼びようがないラムダ式で再帰処理が書きたい場合どうするかです。

引数として「次の処理」ももらうようにする

発想は至極単純です。
次の段階として呼ぶべきメソッドがわからないのが問題なら、それも引数として受け取ることにすれば、とりあえずは記述できます。
こうです。

Func<Func<int, int>, int, int> pow
  = (next, n) => (n > 1) ? n * next(n - 1) : 1;

引数として整数nのほかに「次の処理」nextももらうようにしました。
ラムダ式の型は一気に複雑になりました。

とは言え、この関数はどのように呼べばいいのか? なにしろ、呼び手は「次の処理」nextを仕立ててこれに渡さないといけません。

そこで、この面倒な関数を再帰処理として仕立て直してくれるライブラリ関数をひとつだけ用意することにします。再帰化する処理だからRecurseメソッドと名付けましょう*1。

public static Func<T1, TResult> Recurse<T1, TResult>(Func<Func<T1, TResult>, T1, TResult> f) {
  Func<T1, TResult> next = null;
  return next = (p => f(next, p));
}

これに食わせれば、仮記述したラムダは完全な再帰関数になります。だから、階乗関数をその場で定義してすぐ使う、という処理はこう記述できます。

int result = Recurse<int, int>(
  (next, n) => (n > 1) ? n * next(n - 1) : 1
)(5);

Java版も書きましょう。まず用意しておくrecurseメソッドは

public static <T1, TResult> Function<T1, TResult> recurse(BiFunction<Function<T1, TResult>, T1, TResult> f) {
   return p -> recurseInner(f, p);
}

private static <T1, TResult> TResult recurseInner(final BiFunction<Function<T1, TResult>, T1, TResult> f, T1 p) {
  return f.apply(_p -> recurseInner(f, _p), p);
}

こう。C#版と違って2つのメソッドに分かれてしまっていますね。これは、Java8のラムダがクロージャではなく単なる無名クラス作成のシンタックスシュガーなので*2、ラムダ式中にはfinalな変数しか持ち込めないためです。Java8のラムダ、もう少し頑張ってほしかったですね。

使い方はこうなります。

int result = recurse<Integer, Integer>(
  (next, n) -> (n > 1) ? n * next(n - 1) : 1
).apply(5);
メモ化もしてしまおう

さて、再帰処理のもう一人の代表選手、たらい回し関数にお出ましいただきました。
この関数、評価回数がすぐに爆発するので考えなしに再帰呼び出しすると処理が帰ってこなくなるやつです。

int tarai(int X, int Y, int Z) {
  return X <= Y
    ? Y
    : tarai(tarai(X - 1, Y, Z),
            tarai(Y - 1, Z, X),
            tarai(Z - 1, X, Y));
}

こういう関数の正しい再帰呼び出しの仕方は、メモ化するか遅延評価するかですね。
遅延評価はちょっとC#の枠組みでは大変なので今回パス。
メモ化は、「一度結果の出た計算は（結果を覚えておいて）二度としない」という実行戦略です。
Recurseメソッドをちょっと改造したメモ化対応版を作りましょう。

まず、3引数版のRecurseを用意した上で…

public static Func<T1, T2, T3, TResult> Recurse<T1, T2, T3, TResult>(Func<Func<T1, T2, T3, TResult>, T1, T2, T3, TResult> f) {
  Func<T1, T2, T3, TResult> next = null;
  return next = (p1, p2, p3) => f(next, p1, p2, p3);
}

これのメモ化戦略型、RecurseMemorisedです。

public static Func<T1, T2, T3, TResult> RecurseMemorised<T1, T2, T3, TResult>(Func<Func<T1, T2, T3, TResult>, T1, T2, T3, TResult> f) {
  Dictionary<object, TResult> memory = new Dictionary<object, TResult>();
  Func<T1, T2, T3, TResult> next = null;
  return next = (p1, p2, p3) => memory.ContainsKey(new {p1, p2, p3})
    ? memory[new {p1, p2, p3}]
    : memory[new {p1, p2, p3}] = f(next, p1, p2, p3);
}

呼び出しておきますか?

int result = RecurseMemorised<int, int, int, int>(
  (next, X, Y, Z) =>  X <= Y
    ? Y
    : next(next(X - 1, Y, Z),
           next(Y - 1, Z, X),
           next(Z - 1, X, Y))
)(11, 10, 0);

実行環境をお持ちなら、是非ナイーブ版とメモ化版とで評価回数を比べてみてください。

int result = RecurseMemorised<int, int, int, int>(
  (next, X, Y, Z) =>  (count++) * 0 + (X <= Y
    ? Y
    : next(next(X - 1, Y, Z),
           next(Y - 1, Z, X),
           next(Z - 1, X, Y))
))(11, 10, 0);

なんて書き方すると簡単に評価回数がとれます。

まとめ

やってることは完全に関数プログラミングでよく使う不動点コンビネータそのものなんですけどね。

あわせてどうぞ【Java/C#で解説する関数プログラミング】

*1:"recurse"なんて単語はないよと赤波線つけてくるスペルチェッカもあると思いますが、いちおう英英辞典で「Recursiveからの逆成動詞」という説明を見つけたのでないこともない言葉です。

*2:単なるシンタックスシュガーと言い切っていいかというとコンパイラレベルでは新しい機能だったりするのですが、言語仕様としては等価な無名クラス作成に書き下ろし可能なので、言い切ってしまいます。