## Quick Recap

In the last post, I went through the `zipIndex` example from Rúnar’s paper. The example, `zipIndex`, is implemented in functional style Scala, but it has a huge problem — it is not stack safe. If the input list is too long, `zipIndex` will throw `StackOverflowError`.

## Trampoline

So how do we get around the stack problem? Is there a way to avoid creating stack frames? At this point, the paper introduces a technique called trampoline. The idea is to “trade stack for heap”.

Trampoline
`````` 1
2
3
4
5
6
7
8
9
10
11sealed trait Trampoline[+A] {
@tailrec (1)
final def runT: A =
this match {
case More(k) => k().runT
case Done(v) => v
}
}
case class More[+A](k: () => Trampoline[A])
extends Trampoline[A]
case class Done[+A](result: A) extends Trampoline[A]
``````
 1 Tell the Scala compiler to apply tail-call optimisation. As such, no new stack frame will be created when `runT` calls itself.

`Trampoline` is an ADT that captures the steps of a computation. In order words, given a computation that will return a value of type `A` (correspond to the covariant type variable, `A`, of the above `Trampoline` ADT), that computation can be represented as either `More` or `Done`. A `Done` signifies that computation is finished, and the value inside `Done` will be used as the return value. A `More` indicates that there is a least one more step to perform for the computation. So go ahead and perform the step inside `More`, then see what the next step will be.

As an aside, I much prefer the Haskell syntax; it is much more concise. Below is the implementation of `runT` and the `Trampoline` ADT in Haskell.

``````data Trampoline a = More (() -> Trampoline a)
| Done a

runT :: Trampoline a -> a
runT (Done a) = a
runT (More k) = runT (k ())``````

### Trampoline Example: Odd and Even

After introducing the `Trampoline` ADT, the paper shows a simple example on how to use it. The `odd` and `even` functions do as their names say. They call each other mutual recursively — meaning at the last step of `odd` it calls `even` and vice versa. Since we are using `Trampoline` to represent the `odd` and `even` computations and both of those computations return Boolean, the return types for `odd` and `even` will be `Trampoline[Boolean]`.

Let’s see the code!

`````` 1
2
3
4
5
6
7
8
9
10
11
12
13def even[A](ns: List[A]): Trampoline[Boolean] = (1)
ns match {
case Nil => Done(true)
case x :: xs => More(() => odd(xs)) (2)
}

def odd[A](ns: List[A]): Trampoline[Boolean] = (1)
ns match {
case Nil => Done(false)
case x :: xs => More(() => even(xs)) (2)
}

even(List(1,2,3)).runT // -> False  (3)
``````
 1 Return `Trampoline[Boolean]` rather than just `Boolean`. 2 Mutual recursion. 3 Run the computation.

After calling `even(List(1,2,3))`, we get a value of type `Trampoline[Boolean]`. The value represents all the steps in the `even` computation. So in order to get the `Boolean` value out, we will need to run those steps. Hence, we need to call `runT` on the return value of `even`. This is why we are trading stack for heap. The return value of `even` contains all the computational steps.

Normally, if `even` and `odd` mutually call each other and they return `Boolean` values, the invocation of `even(List.fill(4000)(1))` will overflow the stack. That is because at the end of `even`, before it can return, it calls `odd`. Thus, creating a new stack frame for every single element in the input list. By utilizing `Trampoline`, instead of having `even` calls `odd`, `even` just returns a step (`More`). The last step is to ‘get’ the boolean value out of `Trampoline`. To do that, we call `runT`. Since `runT` is tail recursive, it is not allocating new stack frames.

### Why Is It Called Trampoline?

By using `Trampoline`, the control flow has changed. Originally, `even` passing its control to `odd`, then `odd` passes its control to `even`, in the process, allocates a new stack frame for `even`. The back and forth goes on until it reaches the end of the input list. When `Trampoline` is used as the return value, `even` just returns a value of type `Trampoline`. It is up to the `runT` method of `Trampoline` to call the next step. So the control flow bounces from a function to `Trampoline`, then to another function, then back to `Trampoline` and so on. Every time when the control bounces back to `runT`, the stack frame gets deallocated. So there is no risk of overflowing the stack.

## Applying Trampoline

The logical next step is to apply the `Trampoline` technique to the `zipIndex` example introduced in the first post. And that is what we will see in the next post.