不動点コンビネータを使ってラムダ式で再帰関数を定義する

Javaのラムダ式で再帰関数を書くのはちょっと面倒です。例として、フィボナッチ数列のN番目の項を再帰的に計算する関数（以降フィボナッチ関数）を考えます*1。次のコードはエラーになってしまいます。

IntUnaryOperator fib
  = n -> n <= 1
         ? 1
         : fib.applyAsInt(n - 1) + fib.applyAsInt(n - 2);
// => エラー: 変数fibは初期化されていない可能性があります

代入演算子の右側、ラムダ式内の変数fibが初期化されていない、としてコンパイルエラーになってしまいました。

これは、ラムダ式においてローカル変数がキャプチャされるタイミングを考えると、仕方のないことです。ラムダ式内で参照されるローカル変数は、「実質的にfinal」な変数として、関数オブジェクト生成時にその値が渡されます。つまり、関数オブジェクトが生成されるタイミングで、既に値が決定されている必要があります。上記のコードで変数fibに代入されるのは関数オブジェクトそのものですから、関数オブジェクトが生成されるタイミングでは、まだ値が決まっていません。このためにコンパイルエラーになってしまうわけです。

では、どのようにして再帰関数を定義するか。ひとつの方法は、不動点コンビネータを使うことです。不動点コンビネータとは、外側の変数を参照せずに再帰関数を生成できるような関数です。たとえば、不動点コンビネータとしてfixメソッドを定義したとすると、フィボナッチ関数fibは次のように定義できます。

IntUnaryOperator fib
  = fix(fib2 -> n -> n <= 1
                     ? 1
                     : fib2.applyAsInt(n - 1) + fib2.applyAsInt(n - 2));
System.out.println(fib.applyAsInt(10));  // => 89

不動点コンビネータfixは、「関数 (fib2) を引数にとって関数 (n -> ...) を戻す関数」を引数にとり、関数 (fib) を戻します。ここでポイントは、関数fib2と関数「n -> ...」と関数fibがすべて同じように動作する関数だ、ということです。フィボナッチ関数の本体を定義しているのはラムダ式「n -> ...」ですが、このラムダ式の本体で使われているfib2にも、自分自身と同じように動作するフィボナッチ関数が与えられます。このため、代入演算子の左側にある変数fibにアクセスせずに、再帰的なフィボナッチ関数が定義できるわけです。

fixの定義を含むプログラム全体は次の通りです。ここでは、Zコンビネータと呼ばれる不動点コンビネータを実装しています。

import java.util.function.*;

public class Z {
  @FunctionalInterface
  interface ArgRecusiveFunction<T> {
    T apply(ArgRecusiveFunction<T> r);
  }

  public static IntUnaryOperator
  fix(UnaryOperator<IntUnaryOperator> f) {
    ArgRecusiveFunction<IntUnaryOperator> r
      = rr -> f.apply(a -> rr.apply(rr).applyAsInt(a));
    return r.apply(r);
  }

  public static void main(String[] args) {
    IntUnaryOperator fib
      = fix(fib2 -> n -> n <= 1
                         ? 1
                         : fib2.applyAsInt(n - 1) + fib2.applyAsInt(n - 2));
    System.out.println(fib.applyAsInt(10));
  }
}

不動点コンビネータによって生成される再帰関数は、外側の変数を参照しないので、Streamのメソッドに引数として渡すことが容易です。たとえば、フィボナッチ数列の0番目から100番目までの項を出力するコードは、次のように書けます。

IntStream.rangeClosed(0, 100)
  .map(fix(fib -> n -> n <= 1
                       ? 1
                       : fib.applyAsInt(n - 1) + fib.applyAsInt(n - 2)))
  .forEachOrdered(System.out::println);
// => 1 1 2 3 5 8 13 21 ...

おしむらくは、Javaには一般的な関数型が存在しないため、定義する関数の型ごとに不動点コンビネータを実装する必要があります。IntUnaryOperator用のfix、DoubleUnaryOperator用のfix、Function用のfix……がそれぞれ必要なわけです。

*1:念のため、これはきわめて効率の悪い方法です。