Trampoline style

TrampolineTest.scala

import org.scalatest.{Matchers, FunSuite}

import scala.annotation.tailrec

// https://www.youtube.com/watch?v=hzf3hTUKk8U
// http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html
class TrampolineTest extends FunSuite with Matchers {
	sealed trait Trampoline[A] {
		final def run: A = runImpl(this)

		@tailrec
		private def runImpl[A](t: Trampoline[A]): A = t match {
			case Bounce(jump)   => runImpl(jump())
			case Return(x)      => x
		}
	}

	case class Bounce[A](jump: () => Trampoline[A]) extends Trampoline[A]
	case class Return[A](x: A) extends Trampoline[A]

	def composeAll[A](fs: List[A => A]): A => A =
	    fs.foldLeft((a: A) => a)(_ andThen _)

	def composeAllT[A](fs: List[A => A]): A => A = { (a1: A) =>
		(fs.foldRight(Return(_: A): Trampoline[A]) { (f,r) => (a2: A) =>
			Bounce(() => r(f(a2)))
		})(a1).run
	}

	test("composeAll stackoverflow") {
		val l = (1 to 39355).toList.map { i => ((_: Int) => i) }

		an [StackOverflowError] should be thrownBy composeAll(l)(0)
	}

	test("composeAllT not stackoverflow") {
		val l = (1 to 39355).toList.map { i => ((_: Int) => i) }

		composeAllT(l)(0) shouldBe 39355
	}

	// TODO see continuation passing style
}