Cats の Evalで遅延たらい回し関数を書いてみる

『[ふつうのHaskellプログラミング](https://www.amazon.co.jp/o/ASIN/4797336021/yasuabe1984-22/ref=nosim)』に載ってた「たらい回し関数[^tarai]」を、当時リリースされたばかりの Java 8 を使った遅延評価版で[書いてみた](http://yasutech.blogspot.jp/2014/03/java-8-supplier.html)ことがあるが、ムダな計算がなくなってだいたい千分の一くらい時間で計算が終わるようになった。

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

- ソース: [eval.sc (gist)](https://gist.github.com/yasuabe/6354b29e820cb17feb9a4f4f47363234)

## ふつうのたらい回し関数

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

```scala
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秒かかる。

```scala
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](https://typelevel.org/cats/datatypes/eval.html) はトランポリンを使ったスタックセーフなデータ型で、`val` キーワード相当の *now*、`lazy val` 相当の *later*、`def` 相当の *always* といった 3つの評価戦略がある。以下、これを踏まえてそれぞれみてみる。

### 自然な Eval

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

```scala
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ミリ秒で計算が終わる。

```scala
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`キーワードがついた変数と似た挙動になる。

```scala
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`な変数に対応する[^lazy_difference]。

```scala
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`と似た挙動になる。

```scala
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`を使わなくても「名前渡し」で同様に書ける。

```scala
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 |       -     |

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

[^tarai]: [竹内関数](https://ja.wikipedia.org/wiki/%E7%AB%B9%E5%86%85%E9%96%A2%E6%95%B0)とも言う。もともとムダに計算量を大きくするよう工夫されている事が重宝されてベンチマークなどに使われているので、この記事のように計算量を減らす工夫をするのは、もちろん実務的には意味が無い。あくまでも Eval の遅延評価を試してみるだけの実験。
[^lazy_difference]: `lazy val` と全く同じというわけではなく、ガベージコレクションによる効率的なメモリ使用や、スレッドセーフのためのロックの粒度が小さいと言ったメリットがある。