TCO CPS

[xacid]

import scala.annotation.tailrec
import Thunk._

sealed trait Thunk[A, B] {
  @inline final def run(f: A => B): B = Thunk.run(this, f)
}

object Thunk {

  trait =>>[A, B] {
    @inline final def <<=(a: A) = More(this, a)

    def apply(a: A): Thunk[A, B]
  }

  final case class Done[A](a: A) extends Thunk[A, A]

  final case class More[A, B](k: A =>> B, a: A) extends Thunk[A, B]

  object Return {
    @inline final def apply[A]: A =>> A = Done[A]
  }

  @tailrec final def run[A, B](thunk: Thunk[A, B], f: A => B): B = thunk match {
    case More(k, a) => run(k(a), f)
    case Done(a) => f(a)
  }

  implicit class ThunkOp[A](val thunk: Thunk[A, A]) extends AnyVal {
    @inline final def get() = thunk.run(identity)
  }

}

object CpsTco extends App {

  @tailrec def mkList[T](n: Int)(k: List[Int] => T): List[Int] => T =
    if (n <= 0) k else mkList(n - 1)(l => k(n :: l))

  print("\n`mkList(10)(id)`(Nil) == ")
  println(mkList(10)(identity)(Nil))

  val `mkList(10000)(id)` = mkList(10000)(identity)
  println("\nFunction `mkList(10000)(id)` exists: " + `mkList(10000)(id)`)

  print("\n`mkList(10000)(id)`(Nil) == ")
  try println(`mkList(10000)(id)`(Nil)) catch {
    case t: Throwable => println(t)
      t.getStackTrace().toStream.take(10).foreach(println)
  }

  @tailrec def mkListTco[T](n: Int)(k: List[Int] =>> T): List[Int] =>> T =
    if (n == 0) k else mkListTco(n - 1)(l => k <<= n :: l)

  print("\n`mkListTco(10)(id)`(Nil) == ")
  println(mkListTco(10)(Return[List[Int]])(Nil))

  print("\n`mkListTco(10000)(id)`(Nil) == ")
  println(mkListTco(10000)(Return[List[Int]])(Nil).get())

}