Dependently Typed StateMonad

DepState.scala

//alright, not completely perfect but getting close enough
//Still relying too heavily on Aux types to tie type knots
trait DepState[S]{ self =>
	type R

	def apply(s: S): (S, R)

	def map(f: DepFun1[R]): DepState[S] = new DepState[S]{
		type R = f.R
		def apply(s: S): (S, f.R) ={
			val (s1, a) = self(s)
			(s1, f(a))
		}
	}

	//this implicit gets trickier!
	def flatMap(f: DepFun1[R])(implicit fm: StateMappable[S, f.R]) = new DepState[S]{
		type R = fm.R
		def apply(s: S): (S, fm.R) ={
			val (s1, a) = self(s)
			fm(f(a))(s1)
		}
	}
}

object DepState{
	def apply[S, A](f: DepFun1[S])(implicit ev: f.R =:= (S, A)) = new DepState[S]{
		type R = A

		def apply(s: S) = ev(f(s))
	}

	type Aux[S, R0] = DepState[S]{ type R = R0 }
}

trait StateMappable[S, T]{
	type R

  //if only could lose the .Aux here...
	def apply(t: T): DepState.Aux[S, R]
}

object StateMappable{
	def apply[S, T](implicit fm: StateMappable[S, T]): Aux[S, T, fm.R] = fm

	type Aux[S, T, R0] = StateMappable[S, T]{ type R = R0 }

	implicit def yes[S, R0] = new StateMappable[S, DepState.Aux[S, R0]]{
		type R = R0
		def apply(s: DepState.Aux[S, R0]) = s
	}
}

State.scala

//for reference

trait State[S, A]{ self =>
	def apply(s: S): (S, A)

	def map[B](f: A => B): State[S, B] =new State[S, B]{
		def apply(s: S): (S, B) ={
			val (s1, a) = self(s)
			(s1, f(a))
		}
	}

	def flatMap[B](f: A => State[S, B]): State[S, B] =new State[S, B]{
		def apply(s: S): (S, B) ={
			val (s1, a) = self(s)
			f(a)(s1)
		}
	}
}