fork download
copy 
  1. sealed trait TailRec[A] {
  2.   final def run : A = this match {
  3.     case Return(v)  => v
  4.     case Suspend(k) => k().run
  5.   }
  6. }
  7.  
  8. case class Return[A](v : A) extends TailRec[A]
  9. case class Suspend[A](resume : () => TailRec[A]) extends TailRec[A]
  10.  
  11. object Main {
  12.   def normal (n : Int) : Int =
  13.     if (n == 0) 0
  14.     else 1 + normal(n - 1)
  15.  
  16.   def cps (n : Int) : Int = {
  17.     def loop (i : Int, k : Int => TailRec[Int]) : TailRec[Int] =
  18.       if (i == 0) k(0)
  19.       else loop(i - 1, x => Suspend(() => k(1 + x)))
  20.  
  21.     loop(n, t => Return(t)).run
  22.   }
  23.  
  24.   def accum (n : Int) : Int = {
  25.     def loop (i : Int, a : Int) : Int =
  26.       if (i == 0) a
  27.       else loop(i - 1, a + 1)
  28.  
  29.     loop(n, 0)
  30.   }
  31.  
  32.   def main(args : Array[String]) : Unit = {
  33.     val n = 100
  34.     val s1 = System.currentTimeMillis()
  35.     accum(n)
  36.     println(System.currentTimeMillis() - s1)
  37.  
  38.     val s2 = System.currentTimeMillis()
  39.     cps(n)
  40.     println(System.currentTimeMillis() - s2)
  41.  
  42.     val s3 = System.currentTimeMillis()
  43.     normal(n)
  44.     println(System.currentTimeMillis() - s3)
  45.   }
  46. }
Success #stdin #stdout 0.32s 321984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
206
2
0
https://ideone.com/uuXEcX
language:
Scala (scala 2.12.8)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!