Trampolines in Scala

May 16, 2014

Given the functions:

def odd(x: Int): Boolean =
  if (x == 0) false
  else even(x - 1)

def even(x: Int): Boolean =
  if (x == 0) true
  else odd(x - 1)

We can determine the evenness or the oddness of integers:

println(even(100)) // true
println(even(101)) // false

println(odd(100)) // false
println(odd(101)) // true

But due to the mutual recursion of even and odd, we're limited by our call stack size to evaluating very small numbers:

println(even(100000)) // stack overflow

Convert even and odd to return Trampoline[Boolean] instead of Boolean, and write a tail-recursive interpreter that allows large numbers to be evaluated:

sealed trait Trampoline[+A]
case class Done[+A](a: A) extends Trampoline[A]
case class More[+A](f: () => Trampoline[A]) extends Trampoline[A]

object Trampoline {
  def run[A](t: Trampoline[A]): A = ???
}

Solution

Here is one possible solution.

def oddT(x: Int): Trampoline[Boolean] =
  if (x == 0) Done(false)
  else More(() => evenT(x - 1))

def evenT(x: Int): Trampoline[Boolean] =
  if (x == 0) Done(true)
  else More(() => oddT(x - 1))

object Trampoline {
  def run[A](t: Trampoline[A]): A =
    t match {
      case Done(a) => a
      case More(f) => run(f())
    }
}

println(Trampoline.run(evenT(100000))) // true
println(Trampoline.run(evenT(100001))) // false

println(Trampoline.run(oddT(100000))) // false
println(Trampoline.run(oddT(100001))) // true

Demo

This file is literate Scala, and can be run using Codedown:

$ curl https://earldouglas.com/exercises/scala-trampolines.md |
  codedown scala |
  xargs -0 scala -nc -e
true
false
false
true
true
false
false
true