Int→Bool な無名再帰

前の記事で掲載した型付きZコンビネータは型引数を1つしか取らず，入力と出力の型が一致していなければなりませんでした．しかし，世の中には $\texttt{isEven}$ や $\texttt{isOdd}$ のような $\texttt{int} \to \texttt{bool}$ という型をもつ関数もあります．

このような関数でも無名再帰ができるようにするために，以前のZコンビネータに手を加え，型引数を2つ取るようにしました．完成したコードを以下に示します．

@FunctionalInterface
interface R<X, Y> {
    public X apply(R<X, Y> f);
}

private static <X, Y> Function<X, Y> Z(Function<Function<X, Y>, Function<X, Y>> f) {
    R<Function<X, Y>, Y> x1 = (x) -> {
        return f.apply((X y) -> x.apply(x).apply(y));
    };
    R<Function<X, Y>, Y> x2 = (x) -> {
        return f.apply((X y) -> x.apply(x).apply(y));
    };

    return x1.apply(x2);
}

このZコンビネータを使い $\texttt{isEven}$ と $\texttt{isOdd}$ を実装したものがこちらになります．$\texttt{isEven}$ と $\texttt{isOdd}$ の型が Function<Integer, Boolean> になっており，整数から真偽値への関数となっていることがわかります．

Function<Function<Integer, Boolean>, Function<Integer, Boolean>> _isOdd =
      (Function<Integer, Boolean> f) -> (Integer n) -> n == 0 ? false : !f.apply(n - 1);

Function<Function<Integer, Boolean>, Function<Integer, Boolean>> _isEven =
      (Function<Integer, Boolean> f) -> (Integer n) -> n == 0 ? true : !f.apply(n - 1);


Function<Integer, Boolean> isOdd = Z(_isOdd);
Function<Integer, Boolean> isEven = Z(_isEven);

$\texttt{isEven}$ と $\texttt{isOdd}$　の実装方法はさまざまありますは今回はシンプルな再帰で書くという方法を試しました．他の実装としては，相互再帰を使うやり方があります．名前参照ができないラムダ計算の体系で果たして相互再帰が可能なのか，次はその辺りを探っていきたいと思います．

相互再帰で isOdd と isEven

$$\texttt{fun isOdd n = if n == 0 then false else isEven(n - 1)}\\ \texttt{fun isEven n = if n == 0 then true else isOdd(n - 1)}$$