import language.higherKinds

// Scala doesn't have Identity, so here....
object Id {
  type Identity[+A] = A
  implicit val identityFunctor: Functor[Identity] = new Functor[Identity] {
    def fmap[A, B](f: A => B)(fa: Identity[A]) = f(fa)
  }
}

import Id._

// Scala doesn't have Functors, so here....
trait Functor[F[_]] {
  def fmap[A, B](f: A => B)(m: F[A]): F[B]
}
object Functor {
  def apply[A[_]](implicit ev: Functor[A]) = ev
}

// Coyoneda definition
sealed trait Coyoneda[F[_], A] {
  def map[B](f: A => B): Coyoneda[F, B] = this match {
    case Coyo(g, v) => Coyo(f compose g, v)
  }
}
case class Coyo[F[_], A, B](run: B => A, f: F[B]) extends Coyoneda[F, A]

object Coyoneda {
  def liftCoyoneda[F[_], A](f : F[A]): Coyoneda[F, A] =
    Coyo((a: A) => a, f)

  def lowerCoyoneta[F[_]: Functor, A](coyo: Coyoneda[F, A]): F[A] = coyo match {
    case Coyo(f, m) => Functor[F].fmap(f)(m)
  }

  // Eraser[A] is just a Coyoneda on identity
  type Eraser[A] = Coyoneda[Identity, A]
  def runEraser[A](eraser: Eraser[A]): A = lowerCoyoneta(eraser)
}
// Our typeclass
trait Foo[A] {
  def foo(a: A): String
}
object Foo {
  def apply[A](implicit ev: Foo[A]) = ev

  def fooCoyo[A: Foo](f: A): Coyoneda.Eraser[String] =
    Coyo[Identity, String, A](Foo[A].foo(_: A), f)
}

// Our types
case class Bar(run: Int)
object Bar {
  implicit val foo: Foo[Bar] = new Foo[Bar] {
    def foo(a: Bar) = a.run.toString
  }
}
case class Baz(run: String)
object Baz {
  implicit val foo: Foo[Baz] = new Foo[Baz] {
    def foo(a: Baz) = a.run
  }
}

object Main {
  import Coyoneda._
  import Foo.fooCoyo
  def main = {
    val list: List[Eraser[String]] =
      fooCoyo(Bar(1)) :: fooCoyo(Baz("Hello")) :: Nil
    list.map(runEraser) // Prints List(1, Hello)
  }
}