トランポリン化とアキュムレータの性能比較 ref: http://qiita.com/yyu/items/cd689bf8e61d103c72aa

Counting.scala

import fpinscala.tailrec._

object Counting {
  def normal (n : Int) : Int =
    if (n == 0) 0
    else 1 + normal(n - 1)

  def cps (n : Int) : Int = {
    def loop (i : Int, k : Int => TailRec[Int]) : TailRec[Int] =
      if (i == 0) k(0)
      else loop(i - 1, x => Suspend(() => k(1 + x)))

    loop(n, t => Return(t)).run
  }

  def accum (n : Int) : Int = {
    def loop (i : Int, a : Int) : Int =
      if (i == 0) a
      else loop(i - 1, a + 1)

    loop(n, 0)
  }

  def main(args : Array[String]) : Unit = {
    val n = 100000
    val s1 = System.currentTimeMillis()
    accum(n)
    println(System.currentTimeMillis() - s1)

    val s2 = System.currentTimeMillis()
    cps(n)
    println(System.currentTimeMillis() - s2)

    val s3 = System.currentTimeMillis()
    normal(n)
    println(System.currentTimeMillis() - s3)
  }
}

file2.scala

def main(args : Array[String]) : Unit = {
  def getTime[A] (f : A => Any, i : A, n : Int) : Double = {
    val s = System.currentTimeMillis()
    for (_ <- 1 to n)
      f(i)

    (System.currentTimeMillis() - s).toDouble / n.toDouble
  }

  for (i <- 2 to 7)
    print(s"${getTime(accum, pow(10, i).toInt, 10)},")

  println()

  for (i <- 2 to 7)
    print(s"${getTime(cps, pow(10, i).toInt, 10)},")
}

TailRec.scala

package fpinscala.tailrec

sealed trait TailRec[A] {
  final def run : A = this match {
    case Return(v)  => v
    case Suspend(k) => k().run
  }
}

case class Return[A](v : A) extends TailRec[A]
case class Suspend[A](resume : () => TailRec[A]) extends TailRec[A]