Scala Tutorial - Learn How To Create Trampoline Tail Recursive Function Using scala.util.control.TailCalls._

By Nadim Bahadoor | Last updated: July 25, 2017 at 13:54 pm

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.

This concludes our tutorial on Learn How To Create Trampoline Tail Recursive Function Using scala.util.control.TailCalls._ and I hope you've found it useful!

 

Stay in touch via Facebook and Twitter for upcoming tutorials!

 

Don't forget to like and share this page :)

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

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.

Nadim Bahadoor on FacebookNadim Bahadoor on GithubNadim Bahadoor on LinkedinNadim Bahadoor on Twitter
Nadim Bahadoor
Senior Software Developer | Nephila Capital
Founder of allaboutscala.com. I have over 10 years of experience in building large scale real-time trading systems in the financial industry. Passionate about Distributed Systems, Scala, Big Data and Functional Programming. Stay in touch for upcoming tutorials!
Other allaboutscala.com tutorials you may like:

Share this article on