Javaラムダで竹内関数を書こう

『ふつうのHaskell』を読んでて竹内関数というのが出てきたので、それをJavaでやってみようと思った。

ちなみに竹内関数とは

竹内関数（たけうちかんすう）は、プログラミング言語処理系のベンチマークなどに使われる、再帰的に定義された関数である。
Wikipediaより

らしい。

Haskellでのコード

Haskellだとこんな感じらしい

tak:: Int -> Int -> Int -> Int
tak x y z = when (small x y)
                 y
                 (tak (tak (x - 1) y z)
                      (tak (y - 1) z x)
                      (tak (z - 1) x y))

small:: Int -> Int -> Bool
small x y = x <= y

when:: Bool -> Int -> Int -> Int
when True x y = x
when False x y = y

『ふつうのHaskell』だとHaskellでやると爆速だよ！って書いてあったので、これはJavaでやったらどうなるんだろうと思ったので、Javaでもやるっきゃない！と思った次第であります。

Scalaでの実装

最初、こんな感じに書いてみた

def small (x: Int, y: Int): Boolean = x <= y
def when(c: Boolean, x: Int, y: Int): Int = if(c) x else y
def tak(x: Int, y: Int, z: Int): Int = when(small(x, y), y, tak(tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y)))

実行したら、クソ遅かったのでぐぐってみたら、z: Intのところをz: => Intと書いておくと速くなるらしい。

というわけで、Scalaで竹内関数を速く実行するコードはこんな感じ

def small (x: Int, y: Int): Boolean = x <= y
def when(c: Boolean, x: Int, y: Int): Int = if(c) x else y
def tak(x: Int, y: Int, z: => Int): Int = when(small(x, y), y, tak(tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y)))

これを実行してみたら、Haskellと遜色ない感じの速度になった。

Java

Javaは関数型インターフェースが実装されたからといって、末尾最適化するのが結構大変だった。

きしださんの記事

d.hatena.ne.jp

とか、うらがみさんの記事

backpaper0.github.io

を参考にZコンビネーターって何(´・ω・｀)と思いつつ、とりあえず、コードは真似するかという感じで最初に書いたコードがこれ。

public class 竹内関数 {

    interface TriFunction<X, Y, Z, R> {
        R apply(X x, Y y, Z z);
    }

    interface Tak extends TriFunction<Integer, Integer, Integer, Integer> {}

    interface Dak extends Function<Dak, Tak> {}

    static Tak fpComb(Function<Tak, Tak> f) {
        Function<Dak, Tak> fun = d -> f.apply((x,y,z) -> d.apply(d).apply(x, y, z));
        Dak dak = d -> f.apply((x,y,z) -> d.apply(d).apply(x,y,z));
        return fun.apply(dak);
    }

    @Test
    public void tak() {
        Function<Tak, Tak> function = tak ->
                (x,y,z) ->
                        x <= y ? y : tak.apply(
                                tak.apply(x-1, y, z),
                                tak.apply(y-1, z, x),
                                tak.apply(z-1, x, y));
        Tak tak = fpComb(function);
        System.out.println(tak.apply(20, 10, 5));
    }
}

そして、これを実行してみたものの、やっぱり遅い…(´；ω；｀)ﾌﾞﾜｯ

そこで先ほどのScalaバージョンでやった第三引数だけを遅延評価する方法を採用してみた。

public class 竹内関数 {

    interface TriFunction<X, Y, Z, R> {
        R apply(X x, Y y, Z z);
    }

    interface Tak extends TriFunction<Integer, Integer, Supplier<Integer>, Integer> {}

    interface Dak extends Function<Dak, Tak> {}

    static Tak fpComb(Function<Tak, Tak> f) {
        Function<Dak, Tak> fun = d -> f.apply((x,y,z) -> d.apply(d).apply(x, y, z));
        Dak dak = d -> f.apply((x,y,z) -> d.apply(d).apply(x,y,z));
        return fun.apply(dak);
    }

    @Test
    public void tak() {
        Function<Tak, Tak> function = tak ->
                (x,y,z) ->
                        x <= y ? y : tak.apply(
                                tak.apply(x-1,y,z),
                                tak.apply(y-1,z.get(),() ->x),
                                () -> tak.apply(z.get() -1,x,() -> y));
        Tak tak = fpComb(function);
        System.out.println(tak.apply(20, 10, () -> 5));
    }
}

これを実行すると、Haskellバージョンに遜色ないくらいの速さになった。

やったね！

でも、不動点コンビネーターを理解するほど、僕の頭はSHARPではなかったorz

---

え？Javaのコードで速くなったけど、コードが長い？

まあ、それはアレで

---

おわり