trampoline-overflow.markdown

Initial call

bounce(append(List(1,2,3,4,5),List(6)))

Descend into argument

append(List(1,2,3,4,5),List(6))
bounce(...)

Pattern match (append)

Suspend(() => append(List(2,3,4,5),List(6)) map (1::_))
bounce(...)

Return result from append into bounce

bounce(Suspend(() => append(List(2,3,4,5),List(6)) map (1::_)))

Pattern match (bounce), descend into suspension

append(List(2,3,4,5),List(6)) map (1::_)
bounce(...)

Descend into ... map (1::_)

append(List(2,3,4,5),List(6))
... map (1::_)
bounce(...)

Pattern match (append)

Suspend(() => append(List(3,4,5),List(6)) map (2::_))
... map (1::_)
bounce(...)

Return result from append to ... map (1::_)

Suspend(() => append(List(3,4,5),List(6)) map (2::_)) map (1::_)
bounce(...)

Apply ... map (1::_), descend into suspension

append(List(3,4,5),List(6)) map (2::_)
Suspend(() => ... map (1::_))
bounce(...)

Descend into ... map (2::_)

append(List(3,4,5),List(5,6))
... map (2::_)
Suspend(() => ... map (1::_))
bounce(...)

Pattern match (append)

Suspend(() => append(List(4,5),List(6)) map (3::_))
... map (2::_)
Suspend(() => ... map (1::_))
bounce(...)

Return result from append to ... map (2::_)

Suspend(() => append(List(4,5),List(6)) map (3::_)) map (2::_)
Suspend(() => ... map (1::_))
bounce(...)

Apply ... map (2::_), descend into suspension

append(List(4,5),List(6)) map (3::_)
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Descend into ... map (3::_)

append(List(4,5),List(6))
... map (3::_)
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Pattern match (append)

Suspend(() => append(List(5),List(6)) map (4::_))
... map (3::_)
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Return result from append to ... map (3::_)

Suspend(() => append(List(5),List(6)) map (4::_)) map (3::_)
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Apply ... map (3::_), descend into suspension

append(List(5),List(6)) map (4::_)
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Descend into ... map (4::_)

append(List(5),List(6))
... map (4::_)
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Pattern match (append)

Suspend(() => append(nil,List(6)) map (5::_))
... map (4::_)
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Return result from append to ... map (4::_)

Suspend(() => append(nil,List(6)) map (5::_)) map (4::_)
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Apply ... map (4::_), descend into suspension

append(nil,List(6)) map (5::_)
Suspend(() => ... map (4::_))
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Descend into ... map (4::_)

append(nil,List(6))
... map (5::_)
Suspend(() => ... map (4::_))
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Pattern match (append)

Done(List(6))
... map (5::_)
Suspend(() => ... map (4::_))
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Return result from append to ... map (5::_)

Done(List(6)) map (5::_)
Suspend(() => ... map (4::_))
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Apply ... map (5::_)

Done(List(5,6))
Suspend(() => ... map (4::_))
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Return result

Suspend(() => Done(List(5,6)) map (4::_))
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Return result

Suspend(() => Suspend(() => Done(List(5,6)) map (4::_)) map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Return result

Suspend(() => Suspend(() => Suspend(() => Done(List(5,6)) map (4::_)) map (3::_)) map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Return result

Suspend(() => Suspend(() => Suspend(() => Suspend(() => Done(List(5,6)) map (4::_)) map (3::_)) map (2::_)) map (1::_))
bounce(...)

Return result

bounce(Suspend(() => Suspend(() => Suspend(() => Suspend(() => Done(List(5,6)) map (4::_)) map (3::_)) map (2::_)) map (1::_)))

Pattern match (bounce), descend into suspension

Suspend(() => Suspend(() => Suspend(() => Done(List(5,6)) map (4::_)) map (3::_)) map (2::_)) map (1::_)
bounce(...)

Apply ... map (1::_), descend into suspension

Suspend(() => Suspend(() => Done(List(5,6)) map (4::_)) map (3::_)) map (2::_)
Suspend(() => ... map (1::_))
bounce(...)

Apply ... map (2::_), descend into suspension

Suspend(() => Done(List(5,6)) map (4::_)) map (3::_)
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Apply ... map (3::_), descend into suspension

Done(List(5,6)) map (4::_)
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Apply ... map (4::_)

Done(List(4,5,6))
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Return result

Suspend(() => Done(List(4,5,6)) map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Return result

Suspend(() => Suspend(() => Done(List(4,5,6)) map (3::_)) map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Return result

Suspend(() => Suspend(() => Suspend(() => Done(List(4,5,6)) map (3::_)) map (2::_)) map (1::_))
bounce(...)

Return result

bounce(Suspend(() => Suspend(() => Suspend(() => Done(List(4,5,6)) map (3::_)) map (2::_)) map (1::_)))

Pattern match bounce, descend into suspension

Suspend(() => Suspend(() => Done(List(4,5,6)) map (3::_)) map (2::_)) map (1::_)
bounce(...)

Apply ... map (1::_), descend into suspension

Suspend(() => Done(List(4,5,6)) map (3::_)) map (2::_)
Suspend(() => ... map (1::_))
bounce(...)

Apply ... map (2::_), descend into suspension

Done(List(4,5,6)) map (3::_)
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Apply ... map (3::_)

Done(List(3,4,5,6))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Return result

Suspend(() => Done(List(3,4,5,6)) map (2::_))
Suspend(() => ... map (1::_))
bounce(...)

Return result

Suspend(() => Suspend(() => Done(List(3,4,5,6)) map (2::_)) map (1::_))
bounce(...)

Return result

bounce(Suspend(() => Suspend(() => Done(List(3,4,5,6)) map (2::_)) map (1::_)))

Pattern match (bounce), descend into suspension

Suspend(() => Done(List(3,4,5,6)) map (2::_)) map (1::_)
bounce(...)

Apply ... map (1::_), descend into suspension

Done(List(3,4,5,6)) map (2::_)
Suspend(() => ... map (1::_))
bounce(...)

Apply ... map (2::_)

Done(List(2,3,4,5,6))
Suspend(() => ... map (1::_))
bounce(...)

Return result

Suspend(() => Done(List(2,3,4,5,6)) map (1::_))
bounce(...)

Return result

bounce(Suspend(() => Done(List(2,3,4,5,6)) map (1::_)))

Pattern match (bounce), descend into suspension

Done(List(2,3,4,5,6)) map (1::_)
bounce(...)

Apply ... map (1::_)

Done(List(1,2,3,4,5,6))
bounce(...)

Return result

bounce(Done(List(1,2,3,4,5,6)))

Pattern match (bounce)

List(1,2,3,4,5,6)

Finished.

trampoline-overflow.scala

import scala.annotation.tailrec

trait Trampoline[A] {
  def map[B](f: A => B): Trampoline[B]
}

case class Done[A] (a: A) extends Trampoline[A] {
  override def map[B](f: A => B) = Done(f(a))
}

case class Suspend[A] (suspension: () => Trampoline[A]) extends Trampoline[A] {
  override def map[B](f: A => B) = Suspend(() => suspension() map f)
}

object Trampolines {

  @tailrec
  final def bounce[A](trampoline: Trampoline[A]): A = trampoline match {
    case Suspend(suspension) => bounce(suspension())
    case Done(a) => a
  }

  def append[A](xs: List[A], ys: List[A]): Trampoline[List[A]] = xs match {
    case Nil => Done(ys)
    case x::r => Suspend(() => append(r,ys) map (x::_))
  }

  def main(args: Array[String]) = {
    println(bounce(append((1 to 29999).toList, List(30000))))
  }

}