eval tarai

eval.sc

def measure(f: => Int): (Int, Long) = {
  val start  = System.currentTimeMillis()
  val result = f
  val millis = System.currentTimeMillis() - start
  (result, millis)
}

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))

measure(tarai(20, 10, 5))

import cats.{Always, Eval, Later, Now}
import cats.Eval._
import cats.syntax.apply._
import cats.syntax.flatMap._

def warmup(x: Eval[Double], y: Eval[Double], z: Eval[Double]): Eval[Double] = {
  (x, y).mapN(_ <= _) ifM (y, warmup(warmup(Now(   x.value - 0.01), y, z),
                                     warmup(Later( y.value - 0.01), z, x),
                                     warmup(Always(z.value - 0.01), x, y)))
}
warmup(Now(0.4), Later(0.2), Always(0.1)).value

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)))

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
}
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
}
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
}
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 me = measure { taraiE(Now(20), Now(20), Now(5)).value }

val mn = measure { taraiN(Now(20), Now(10), Now(5)).value }
val ml = measure { taraiL(Later(20), Later(10), Later(5)).value }
val ma = measure { taraiA(Always(20), Always(10), Always(5)).value }

val mz = measure(taraiZ(20, 10, 5))

//me: (Int, Long) = (20,4)

//mn: (Int, Long) = (20,43130)
//ml: (Int, Long) = (20,10)
//ma: (Int, Long) = (20,11)

//mz: (Int, Long) = (20,7)