『ふつうの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は関数型インターフェースが実装されたからといって、末尾最適化するのが結構大変だった。
きしださんの記事
とか、うらがみさんの記事
を参考に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のコードで速くなったけど、コードが長い?
まあ、それはアレで
おわり