短いまとめ
ラムダ式を使ってメモ化再帰をする方法を記述しました。
class Lambdas{
static <T,R> Function<T,R> memorizeRec(BiFunction<Function<T,R>, T, R> biFunc){
return memorizeRec(new HashMap<>(), biFunc);
}
static <T,R> Function<T,R> memorizeRec(Map<T,R> memo, BiFunction<Function<T,R>, T, R> biFunc){
return t -> {
if(!memo.containsKey(t)) memo.put(t, biFunc.apply(memorizeRec(memo, biFunc), t));
return memo.get(t);
};
}
}
Function<Integer,Long> fib = Lambdas.memorizeRec( (self,x) -> (x <= 2) ? 1 : self.apply(x-1) + self.apply(x-2) );
fib.apply(50);
// argument: 50 => result: 12586269025
以上です。以下から本文です。
ラムダ式と仲良くなろう
Java 8のリリース（2014/3）から６年以上が経ち、Java 7以前のコードを読み書きすることが身の回りでもほとんどなくなってきました。かつての（Java ７以前の）コーディング環境と比べると、一番の違いは、やはりラムダ式（とFunctional interface）が導入されたことによる変化であるように感じます。
ラムダ式によって振る舞いの記述が容易になったことにより、これまで継承やインタフェースを用いて実現してきたようなデザインパターンも少ない記述で簡潔に実現できるようになった一方で、モダンなJavaやラムダ式に馴染みの無いコーダーにとっては障壁ともなってきました。より良いコードを書くためには、ラムダ式と仲良くして活用していくことが大事だと思います。
Function<Integer, Integer> increment = x -> x + 1;
increment.apply(1);
// argument: 1 => result: 2
今回はラムダ式を使ってできることを増やすために、(1) メモ化、(2) 再帰、(3) メモ化再帰を実現するヘルパーメソッドを紹介します。
メモ化（キャッシュ）
（関数の）メモ化とは、計算した関数の入出力を記憶しておいて、同じ入力が与えられた場合に記憶しておいた出力を返すことで、同じ計算が一度で行えるようにするテクニックです。
HashMapを用いて実装するのが最も簡潔であると思います。
class Lambdas{
static <T,R> Function<T,R> memorize(Function<T,R> func){
Map<T,R> memo = new HashMap<>();
return t -> memo.computeIfAbsent(t, tt -> func.apply(tt));
}
}
Function<Integer, Integer> memo = Lambdas.memorize(x -> x+1);
// argument: 1 => result: 2
メモ化によって計算時間が短縮されるのみでなく、同一インスタンスが返されることからメモリ使用量についても改善が見込ます。（同様に、同一のインスタンスが参照されることから、返り値などは不変な（Immutable）オブジェクトであるかどうかに注意してください）
再帰
話題は変わって、再帰関数についてです。実はラムダ式（無名関数）ではそのままでは再帰関数を記述することができません。例えば階乗の計算を行うとき、名前付きのメソッドであればint fact(n){return (n > 0) ? n * fact(n-1) : 1;}のように記述できますが、ラムダ式にしようとしてみると、Function<Integer, Integer> fact = n -> (n > 0) ? n * ???(n-1) : 1; となって、???部分に入れられる名前がないことがわかります。(factはまだ定義されていないので参照できない)
そのままでは再帰呼び出しできず困ってしまうので、最終的に作成したい関数を外から与えられると仮定しましょう（そんな仮定ができるなら関数作る必要がないではないか、というのはおいといて）。引数にFunction<Integer, Integer>が増えることとなるので、このようになります。
BiFunction<Function<Integer, Integer>, Integer, Integer> fact =
(self, n) -> (n > 0) ? n * self.apply(n-1) : 1;
しかしこのままでは、factに与える第一引数が存在せず、呼び出すことはできません。作成したい関数も Function<Integer, Integer> ですから、上手い具合に先のBiFunction<Function<T,R>, T, R>を変換してFunction<T, R>にしたいです（階乗の例ではT,RともにInteger）。
そこで以下のような変換を施すと上手い具合に変換することができます。
class Lambdas{
static <T,R> Function<T,R> rec(BiFunction<Function<T,R>, T, R> biFunc){
return t -> biFunc.apply(rec(biFunc), t);
}
}
Function<Integer, Integer> fact = Lambdas.rec((self, n) -> (n > 0) ? n * self.apply(n-1) : 1);
// argument: 5 => result: 120
パズルのように複雑ですが、１ステップずつ実際に値を入れて追ってみると良いと思います。
（不動点コンビネータに似た形をしています。興味がある人はぜひ調べてみてください。recはそのまま再帰させているので不動点コンビネータではありませんが。）
メモ化再帰
メモ化再帰とは、再帰関数に対してメモ化を行うことで効率的に計算を行う技法です。例えば(高い次数の)漸化式で表せる数列の特定の項を求める際に、再帰を用いることで式を表すことができますがそのまま計算すると同一項の計算が繰り返し発生し計算量が多くなる場合があります。メモ化再帰を行うことで、同一項については一度のみ計算することですむようにできます。
間違えられやすい点として、再帰関数をメモ化してもメモ化再帰にはなりません。その場合特定の引数に対する呼び出しは早くなりますが、再帰計算自体は遅いままになっていまいます。正しくはメモ化した関数に対して再帰的呼び出しを行う必要があります。
そのため、予めメモ化用のMapを用意して、再帰呼び出しされるごとにメモを参照するようにします。
class Lambdas{
static <T,R> Function<T,R> memorizeRec(BiFunction<Function<T,R>, T, R> biFunc){
return memorizeRec(new HashMap<>(), biFunc);
}
static <T,R> Function<T,R> memorizeRec(Map<T,R> memo, BiFunction<Function<T,R>, T, R> biFunc){
return t -> {
if(!memo.containsKey(t)) memo.put(t, biFunc.apply(memorizeRec(memo, biFunc), t));
return memo.get(t);
};
}
}
Function<Integer,Long> fib = Lambdas.memorizeRec( (self,x) -> (x <= 2) ? 1 : self.apply(x-1) + self.apply(x-2) );
fib.apply(50);
// argument: 50 => result: 12586269025
memorizeRec(Map<T,R>, BiFunction<Function<T,R>,T,R>)の実装部分について、意味合いとしては（＝やりたいことは）、computeIfAbsentと等価ですが、computeIfAbsentの中で再帰が発生して値を書き換えることとなるためConcurrentModificationExceptionが発生してしまいます。そのためcomputeIfAbsentを使用せずcontainsKeyとputによる実装を行っています。