『ふつうのHaskellプログラミング』に載ってた「たらい回し関数¹」を、当時リリースされたばかりの Java 8 を使った遅延評価版で書いてみたことがあるが、ムダな計算がなくなってだいたい千分の一くらい時間で計算が終わるようになった。

今回は、これを Cats のEvalを用いて書いてみる。Scala は2.12.8、Cats は1.6.0を使った。

ソース: eval.sc (gist)

ふつうのたらい回し関数

ふつうに Scala でtaraiを書くと以下のようになる。

def tarai(x: Int, y: Int, z: Int): Int =
  if (x <= y) y else tarai(tarai(x - 1, y, z),
                           tarai(y - 1, z, x),
                           tarai(z - 1, x, y))

このマシン(4G の MBA) の IntelliJ Scala Worksheetから、(20, 10, 5)を与えて実行すると 6〜7秒かかる。

def measure(f: => Int): (Int, Long) = {
  val start  = System.currentTimeMillis()
  val result = f
  val millis = System.currentTimeMillis() - start
  (result, millis)
}
measure(tarai(20, 10, 5))
//res0: (Int, Long) = (20,6076)

次に Evalを用いて、この遅延評価版を書いてみる。

Eval 版

Eval はトランポリンを使ったスタックセーフなデータ型で、val キーワード相当の now、lazy val 相当の later、def 相当の always といった 3つの評価戦略がある。以下、これを踏まえてそれぞれみてみる。

自然な Eval

何通りか書き方があるがここでは以下のように書いてみた。

def taraiE(x: Eval[Int], y: Eval[Int], z: Eval[Int]): Eval[Int] =
  (x, y).mapN(_ <= _) ifM (y, taraiE(taraiE(x.map(_ - 1), y, z),
                                     taraiE(y.map(_ - 1), z, x),
                                     taraiE(z.map(_ - 1), x, y)))

xとyのペアを apply 構文のmapNで大小比較してから、flatMap 構文のifMで条件分岐させた。デクリメントするところはmapを使用しているが、mapの実装ではEval.FlatMapとNowを組み合わせたようなインスタンスが生成されている。

以下のようにすると、実行のたびにかなりバラつくが 2〜8ミリ秒で計算が終わる。

val me = measure { taraiE(Now(20), Now(20), Now(5)).value }
//me: (Int, Long) = (20,2)

ここではEvalの派生クラスNowで渡しているが、Later、Alwaysでも結果はあまり変わらない。

以下のように、mapをつかわず型をNow、Later、Alwaysに固定したtaraiを書くこともできる。

Now 固定

Nowは、eager 評価かつメモ化される。純正な Scala の構文でいえばvalキーワードがついた変数と似た挙動になる。

def taraiN(x: Now[Int], y: Now[Int], z: Now[Int]): Now[Int] = Now {
  if (x.value <= y.value) y.value
  else taraiN(taraiN(Now(x.value - 1), y, z),
              taraiN(Now(y.value - 1), z, x),
              taraiN(Now(z.value - 1), x, y)).value
}
val mn = measure { taraiN(Now(20), Now(10), Now(5)).value }
//mn: (Int, Long) = (20,37578)

即時評価なためオリジナルのtaraiと同様無駄な計算も評価されてしまうため遅い。むしろオリジナルと比べて6倍ほども時間がかかっている。

Later 固定

Laterもメモ化されるが、lazy に評価される。Scalaの構文だとlazy valな変数に対応する²。

def taraiL(x: Later[Int], y: Later[Int], z: Later[Int]): Later[Int] = Later {
  if (x.value <= y.value) y.value
  else taraiL(taraiL(Later(x.value - 1), y, z),
              taraiL(Later(y.value - 1), z, x),
              taraiL(Later(z.value - 1), x, y)).value
}
val ml = measure { taraiL(Later(20), Later(10), Later(5)).value }
//ml: (Int, Long) = (20,11)

遅延評価＋メモ化で速い。

Always 固定

Alwaysも lazy な評価だが、これはメモ化されない。def、()=>Int、Function0と似た挙動になる。

def taraiA(x: Always[Int], y: Always[Int], z: Always[Int]): Always[Int] = Always {
  if (x.value <= y.value) y.value
  else taraiA(taraiA(Always(x.value - 1), y, z),
              taraiA(Always(y.value - 1), z, x),
              taraiA(Always(z.value - 1), x, y)).value
}
val ma = measure { taraiA(Always(20), Always(10), Always(5)).value }
//ma: (Int, Long) = (20,8)

これも遅延評価されていて必要な値のみが計算されるので速い。メモ化はされないがこの例ではあまり影響がない。

名前渡し版

実はEvalを使わなくても「名前渡し」で同様に書ける。

def taraiZ(x: => Int, y: => Int, z: => Int): Int =
  if (x <= y) y else taraiZ(taraiZ(x - 1, y, z),
                            taraiZ(y - 1, z, x),
                            taraiZ(z - 1, x, y))
val mz = measure(taraiZ(20, 10, 5))
//mz: (Int, Long) = (20,9)

これも速い。メモ化しない遅延評価だからAlwaysに近い。

まとめ

タイプ	遅延	メモ	時間	備考
オリジナル	×	×	6〜7sec	-
自然な Eval	-	-	2〜8ms	Eval.FlatMap
Now	×	○	30〜40sec	val 相当
Later	○	○	5〜20ms	`lazy val` 相当
Always	○	×	5〜20ms	`def`、`()=>Int` 相当
名前渡し	○	×	5〜20ms	-

※ 「時間」は何度か実行してからの目分量。

竹内関数とも言う。もともとムダに計算量を大きくするよう工夫されている事が重宝されてベンチマークなどに使われているので、この記事のように計算量を減らす工夫をするのは、もちろん実務的には意味が無い。あくまでも Eval の遅延評価を試してみるだけの実験。 ↩
lazy val と全く同じというわけではなく、ガベージコレクションによる効率的なメモリ使用や、スレッドセーフのためのロックの粒度が小さいと言ったメリットがある。 ↩