Eval データ型 

Cats には、Eval という評価を制御するデータ型がある。

sealed abstract class Eval[+A] extends Serializable { self =>

  /**
   * Evaluate the computation and return an A value.
   *
   * For lazy instances (Later, Always), any necessary computation
   * will be performed at this point. For eager instances (Now), a
   * value will be immediately returned.
   */
  def value: A

  /**
   * Ensure that the result of the computation (if any) will be
   * memoized.
   *
   * Practically, this means that when called on an Always[A] a
   * Later[A] with an equivalent computation will be returned.
   */
  def memoize: Eval[A]
}

Eval 値を作成するにはいくつかの方法がある:

object Eval extends EvalInstances {

  /**
   * Construct an eager Eval[A] value (i.e. Now[A]).
   */
  def now[A](a: A): Eval[A] = Now(a)

  /**
   * Construct a lazy Eval[A] value with caching (i.e. Later[A]).
   */
  def later[A](a: => A): Eval[A] = new Later(a _)

  /**
   * Construct a lazy Eval[A] value without caching (i.e. Always[A]).
   */
  def always[A](a: => A): Eval[A] = new Always(a _)

  /**
   * Defer a computation which produces an Eval[A] value.
   *
   * This is useful when you want to delay execution of an expression
   * which produces an Eval[A] value. Like .flatMap, it is stack-safe.
   */
  def defer[A](a: => Eval[A]): Eval[A] =
    new Eval.Call[A](a _) {}

  /**
   * Static Eval instances for some common values.
   *
   * These can be useful in cases where the same values may be needed
   * many times.
   */
  val Unit: Eval[Unit] = Now(())
  val True: Eval[Boolean] = Now(true)
  val False: Eval[Boolean] = Now(false)
  val Zero: Eval[Int] = Now(0)
  val One: Eval[Int] = Now(1)

  ....
}

Eval.later 

最も便利なのは、Eval.later で、これは名前渡しのパラメータを lazy val で捕獲している。

import cats._, cats.data._, cats.syntax.all._

var g: Int = 0
// g: Int = 0

val x = Eval.later {
  g = g + 1
  g
}
// x: Eval[Int] = cats.Later@1db44b96

g = 2

x.value
// res1: Int = 3

x.value
// res2: Int = 3

value はキャッシュされているため、2回目の評価は走らない。

Eval.now 

Eval.now は即座に評価され結果はフィールドにて捕獲されるため、これも 2回目の評価は走らない。

val y = Eval.now {
  g = g + 1
  g
}
// y: Eval[Int] = Now(value = 4)

y.value
// res3: Int = 4

y.value
// res4: Int = 4

Eval.always 

Eval.always はキャッシュしない。

val z = Eval.always {
  g = g + 1
  g
}
// z: Eval[Int] = cats.Always@2d0e17d4

z.value
// res5: Int = 5

z.value
// res6: Int = 6

スタックセーフな遅延演算 

Eval の便利な機能は内部でトランポリンを使った map と flatMap により、スタックセーフな遅延演算をサポートすることだ。つまりスタックオーバーフローを回避できる。

また、Eval[A] を返す計算を遅延させるために Eval.defer というものもある。例えば、List の foldRight はそれを使って実装されている:

def foldRight[A, B](fa: List[A], lb: Eval[B])(f: (A, Eval[B]) => Eval[B]): Eval[B] = {
  def loop(as: List[A]): Eval[B] =
    as match {
      case Nil => lb
      case h :: t => f(h, Eval.defer(loop(t)))
    }
  Eval.defer(loop(fa))
}

まずはわざとスタックを溢れさせてみよう:

scala> :paste
object OddEven0 {
  def odd(n: Int): String = even(n - 1)
  def even(n: Int): String = if (n <= 0) "done" else odd(n - 1)
}

// Exiting paste mode, now interpreting.

defined object OddEven0

scala> OddEven0.even(200000)
java.lang.StackOverflowError
  at OddEven0$.even(<console>:15)
  at OddEven0$.odd(<console>:14)
  at OddEven0$.even(<console>:15)
  at OddEven0$.odd(<console>:14)
  at OddEven0$.even(<console>:15)
  ....

安全版を書いてみるとこうなった:

object OddEven1 {
  def odd(n: Int): Eval[String] = Eval.defer {even(n - 1)}
  def even(n: Int): Eval[String] =
    Eval.now { n <= 0 } flatMap {
      case true => Eval.now {"done"}
      case _    => Eval.defer { odd(n - 1) }
    }
}

OddEven1.even(200000).value
// res7: String = "done"

初期の Cats のバージョンだと上のコードでもスタックオーバーフローが発生していたが、David Gregory さんが #769 で修正してくれたので、このままで動作するようになったみたいだ。