Scala Tutorial - Learn How To Create Trampoline Tail Recursive Function Using scala.util.control.TailCalls._
Overview
In this tutorial, we will learn how to create trampoline tail recursive function by making use of utilities that Scala provides for tail recursions in the package scala.util.control.TailCalls._
Say you had two tail recursive functions F(A) and F(B) and that F(A) calls F(B) but in turn F(B) also calls F(A).
Then F(A) is said to be a trampoline tail recursive function because the call stack jumps back and forth between the two functions F(A) and F(B) - hence the name trampoline.
As a reminder from the previous tutorial on Tail Recursive Function, tail recursive function will help prevent overflow in your call stack because the evaluation of your looping construct happens at each step.
This tutorial will also make use of TailRec which we have seen from the previous tutorial on How to Create Tail Recursive Function using scala.util.control.TailCalls.
Steps
1. How to define a trampoline function using scala.util.control.TailCalls
Let's start by creating a tail recursive function verySweetDonut() which will return true if the first item in its donutList parameter is a Vanilla, Strawberry or Glazed Donut.
If however a sweet donut is not found, the verySweetDonut() function will call another tail recursive function named notSweetDonut() which we will define in step 2.
println("Step 1: How to define a trampoline function using scala.util.control.TailCalls")
def verySweetDonut(donutList: List[String]): TailRec[Boolean] = {
println(s"verySweetDonut function: donut list = $donutList")
if (donutList.isEmpty) {
println("verySweetDonut function: donut list isEmpty, returning false")
done(false)
} else {
if(Set(donutList.head).subsetOf(Set("Vanilla Donut","Strawberry Donut","Glazed Donut"))) {
println(s"verySweetDonut function: found donut list's head = ${donutList.head} to be VERY sweet, returning true")
done(true)
} else {
println(s"verySweetDonut function: donut list's head = ${donutList.head} is NOT VERY sweet, forwarding donut list's to notSweetDonut function")
tailcall(notSweetDonut(donutList))
}
}
}
NOTE:
- verySweetDonut() function is making use of TailRec, done and tailcall utilities from scala.util.control.TailCalls._ which should be familiar to you from the previous tutorial.
- The important thing to note here is that verySweetDonut() function calls notSweetDonut() function
tailcall(notSweetDonut(donutList))defined in Step 2 below.
2. How to define a trampoline function using scala.util.control.TailCalls
To keep the example simple, we'll assume that the notSweetDonut() function below will log the first donut from its donutList parameter
println(s"notSweetDonut function: donut list's head = ${donutList.head} is NOT sweet, forwarding donut list's tail to verySweetDonut function")
It will then pass back the tail of the donut list to the verySweetDonut() function tailcall(verySweetDonut(donutList.tail))
But if you recall from Step 1 above, the function verySweetDonut() will check the head of the donut list and if it does not find a sweet donut, it will call back the notSweetDonut() function.
This jumping back and forth between verySweetDonut() and notSweetDonut() functions is the trampoline effect.
println("\nStep 2: How to define a trampoline function using scala.util.control.TailCalls")
def notSweetDonut(donutList: List[String]): TailRec[Boolean] = {
println(s"notSweetDonut function: with donut list = $donutList")
if (donutList.isEmpty) {
println("notSweetDonut function: donut list isEmpty, returning false")
done(false)
} else {
println(s"notSweetDonut function: donut list's head = ${donutList.head} is NOT sweet, forwarding donut list's tail to verySweetDonut function")
tailcall(verySweetDonut(donutList.tail))
}
}
3. How to call a trampoline tail recursive function
Simply make use of tailcall() function from scala.util.control.TailCalls._ and pass it the verySweetDonut() function which takes a List of donuts of type String.
println("\nStep 3: How to call a trampoline tail recursive function")
val donutList: List[String] = List("Plain Donut", "Strawberry Donut", "Plain Donut", "Glazed Donut")
val foundVerySweetDonut = tailcall(verySweetDonut(donutList)).result
println(s"Found very sweet donut = $foundVerySweetDonut")
You should see the following output when you run your Scala application in IntelliJ:
Step 3: How to call a trampoline tail recursive function
verySweetDonut function: donut list = List(Plain Donut, Strawberry Donut, Plain Donut, Glazed Donut)
verySweetDonut function: donut list's head = Plain Donut is NOT VERY sweet, forwarding donut list's to notSweetDonut function
notSweetDonut function: with donut list = List(Plain Donut, Strawberry Donut, Plain Donut, Glazed Donut)
notSweetDonut function: donut list's head = Plain Donut is NOT sweet, forwarding donut list's tail to verySweetDonut function
verySweetDonut function: donut list = List(Strawberry Donut, Plain Donut, Glazed Donut)
verySweetDonut function: found donut list's head = Strawberry Donut to be VERY sweet, returning true
Found very sweet donut = true
NOTE:
- Notice how the function call is jumping between verySweetDonut() and notSweetDonut() functions.
Summary
In this tutorial, we went over the following:
- How to define a trampoline function using scala.util.control.TailCalls
- How to call a trampoline tail recursive function
Tip
- You can learn more about Trampoline Tail Recursive function from the Scala documentation on scala.util.control.TailCalls.
- You can read the StackOverflow answer on TailCalls to better understand compiler optimisation for recursive function.
Source Code
The source code is available on the allaboutscala GitHub repository.
What's Next
In the next tutorial, I will show you how to create Partial Function.
