Trampolines

trampolines.scala

import scala.annotation.tailrec

object Trampolines {

  // This is the regular one, and it stack overflows at a couple of 100k input.
  object Stack {
    def even(i: Int): Boolean = i match {
      case 0 => true
      case other => odd(i - 1)
    }

    def odd(i: Int): Boolean = i match {
      case 0 => false
      case other => even(i - 1)
    }
  }

  object Trampoline {

    sealed trait EvenOdd
    case class Done(result: Boolean) extends EvenOdd
    case class Even(value: Int) extends EvenOdd
    case class Odd(value: Int) extends EvenOdd

    def even(i: Int): EvenOdd = i match {
      case 0 => Done(true)
      case other => Odd(i - 1)
    }

    def odd(i: Int): EvenOdd = i match {
      case 0 => Done(false)
      case other => Even(i - 1)
    }

    // Using Scala's self recursive tail call optimization
    @tailrec
    def run(evenOdd: EvenOdd): Boolean = evenOdd match {
      case Done(result) => result
      case Even(value) => run(even(value))
      case Odd(value) => run(odd(value))
    }
  }

  object GeneralTrampolines {

    sealed trait Computation[A]
    class Continue[A](n: => Computation[A]) extends Computation[A] {
      lazy val next = n
    }
    case class Done[A](result: A) extends Computation[A]

    def even(i: Int): Computation[Boolean] = i match {
      case 0 => Done(true)
      case other => new Continue(odd(i - 1))
    }

    def odd(i: Int): Computation[Boolean] = i match {
      case 0 => Done(false)
      case other => new Continue(even(i - 1))
    }

    @tailrec
    def run[A](computation: Computation[A]): A = computation match {
      case Done(a) => a
      case c: Continue[A] => run(c.next)
    }

  }

  object ExceptionTrampolines {

    class Continue[A](n: => A) extends Throwable {
      def next = n
    }

    def cont[A](n: => A): A = throw new Continue(n)

    def even(i: Int): Boolean = i match {
      case 0 => true
      case other => cont(odd(i - 1))
    }

    def odd(i: Int): Boolean = i match {
      case 0 => false
      case other => cont(even(i - 1))
    }

    @tailrec
    def run[A](c: => A): A =
      try c
      catch {
        case e: Continue[A] => run(e.next)
      }
  }

}