# 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