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 = ???
}
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 =
match {
t 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
This file is literate Scala, and can be run using Codedown:
$ curl https://earldouglas.com/posts/exercises/scala-trampolines.md |
codedown scala |
xargs -0 scala -nc -e
true
false
false
true
true
false
false
true