Dependently typed Trampoline (WIP, just jotting my ideas down)

With.scala

import shapeless._
import poly._

trait Next[T]{
  type R <: Trampoline
  def apply(t: T): R
}

object Next{
  def apply[T](implicit nxt: Next[T]): Aux[T, nxt.R] = nxt

  type Aux[T0, R0] = Next[T0]{ type R = R0 }

  implicit def done[R0]: Aux[Done[R0], Done[R0]] = new Next[Done[R0]]{
    type R = Done[R0]

    def apply(r: Done[R0]) = r
  }

  implicit def suspend[T <: Trampoline]: Aux[Suspend[T], T] = new Next[Suspend[T]]{
    type R = T

    def apply(s: Suspend[T]) = s.t()
  }

  implicit def fmDone[T, P <: Poly, R0 <: Trampoline]
    (implicit ev: Case1.Aux[P, T, R0]): Aux[FM[Done[T], P], ev.Result] =
      new Next[FM[Done[T], P]]{
        type R = R0

        def apply(fm: FM[T, P]) = ev(fm.t)
      }

  implicit def fmSuspend[T <: Trampoline, P <: Poly]
    (implicit nxt: Next.Aux[Suspend[T], T]): Aux[FM[Suspend[T], P], FM[T, P]] =
      new Next[FM[Suspend[T], P]]{
        type R = FM[T, P]

        def apply(fm: FM[Suspend[T], P]) = FM(nxt(fm.t), fm.p)
      }

  implicit def fmFM[P <: Poly, T0 <: Trampoline, P0 <: Poly]
    (implicit nxt: Next[FM[T0, P0]]): Aux[FM[FM[T0, P0], P], FM[nxt.R, P]] =
      new Next[FM[FM[T0, P0], P]]{
        type R = FM[nxt.R, P]

        def apply(fm: FM[FM[T0, P0], P]) = FM(nxt(fm.t), fm.p)
      }
}

trait Runner[T]{
  type R

  def apply(t: T): R
}

object Runner{
  def apply[T](implicit run: Runner[T]): Aux[T, run.R] = run

  type Aux[T0, R0] = Runner[T0]{ type R = R0 }

  implicit def done[T]: Aux[Done[T], T] = new Runner[Done[T]] {
    type R = T

    def apply(t: Done[T]) = t.r
  }

  //...and here I go, stack overflow in T-minus 64k calls...
  implicit def continue[T <: Trampoline, R <: Trampoline]
    (implicit run: Runner[R], nxt: Next.Aux[T, R]): Aux[T, run.R] =
      new Runner[T]{
        type R = run.R

        def apply(t: T) = run(nxt(t))
      }
}

trait Trampoline{
  //ok, like this it really does subvert the entire point of a trampoline. There's got to be a better way...
  def run(implicit r: Runner[this.type]): r.R = r(this)

  //need constraints on this. As is, can add a Poly that can't actually ever be "run."
  def map(p: Poly): Trampoline = FM(this, p compose (Done(_)))
  def flatMap(p: Poly): Trampoline = FM(this, p)
}

case class Done[R](r: R) extends Trampoline
case class Suspend[T <: Trampoline](t: () => T) extends Trampoline
case class FM[T <: Trampoline, P <: Poly](t: T, p: P) extends Trampoline

Without.scala

//Made this file for reference

trait Trampoline[R]{
	def run(): R ={
		@tailrec walk(current: Trampoline[R]): R = current match{
			case Done(v) => v
			case x => walk(x next ())
		}
		
		walk(next())
	}
	def map[Out](f: R => Out): Trampoline[Out] = flatMap(x => Done(f(x)))
	def flatMap[Out](f: R => Trampoline[Out]): Trampoline[Out] = FM(this, f)
	
	protected def next(): Trampoline[R]
}

case class Done[R](r: R) extends Trampoline[R]{
	override def run() = r
	override def map[Out](f: R => Out) = Done(f(r))
	override def flatMap[Out](f: R => Trampoline[Out]) = f(r)
	
	protected def next() = this
}

case class Suspend[R](t: => Trampoline[R]) extends Trampoline[R]{
	protected def next() = t
}

case class FM[T, R](t: Trampoline[T], f: T => Trampoline[R]) extends Trampoline[R]{
	protected def next(): Trampoline[R] = t next () match{
		case Done(v) => f(v)
		case v => FM(v, f)
	}
}