BoxCodensityYoneda.scala

import cats._
import cats.implicits._

/*
            Box a: forall b. (a -> b)   -> b
    Codensity f a: forall b. (a -> f b) -> f b
       Yoneda f a: forall b. (a -> b)   -> f b

    https://stackoverflow.com/questions/45287954/is-having-a-a-b-b-equivalent-to-having-an-a
 */

 /*
    We can interpret the end form of Yoneda lemma as an isomorphism between types
    f x and ∀y. (x → y) → f y whenever f is a Functor.

    The components of the isomorphism are implemented as

    ϕ :: Functor f ⇒ f x → (∀y. (x → y) → f y)
    ϕ v = λf → fmap f v

    ϕ −1 :: (∀y. (x → y) → f y) → f x
    ϕ −1 g = g id

    Similarly, its coend form (also known as “coYoneda lemma”) is expressed by

    ψ :: Functor f ⇒ f x → (∃ y. (f y,y → x))
    ψ v = (v,id)

    ψ −1 :: Functor f ⇒ (∃ y. (f y,y → x)) → f x
    ψ −1 (x,g) = fmap g x

    Notions of Computation as Monoids
    https://arxiv.org/pdf/1406.4823.pdf
  */

/** Box a: forall b. (a -> b) -> b */
sealed trait Box[A] {
  def apply[B](f: A => B): B

  def unbox(): A = apply(identity)
}

object Box {
  def apply[A](a: A): Box[A] =
    new Box[A] {
      def apply[B](f: A => B): B = f(a)
    }

  implicit val monad: Monad[Box] =
    new StackSafeMonad[Box] {
      def pure[A](a: A): Box[A] = Box(a)
      def flatMap[A, B](fa: Box[A])(f: A => Box[B]): Box[B] = fa(f)
    }
}

/** `Codensity f a`: `forall b. (a -> f b) -> f b`
 * 
 * `Codensity f` is a monad even after we forget `F` was one.
 * 
 * Codensity is a monad, while its dual, Density, is a comonad.
 */
sealed trait Codensity[F[_], A] {
  def apply[B](f: A => F[B]): F[B]

  def run(implicit monad: Monad[F]): F[A] = apply(_.pure[F])
}

object Codensity {
  def apply[F[_] : Monad, A](fa: F[A]): Codensity[F, A] =
    new Codensity[F, A] {
      def apply[B](f: A => F[B]) = Monad[F].flatMap(fa)(f)
    }

  /** `Codensity` is a monad even after we forget `F` was one. */
  implicit def monad[F[_] : Monad]: Monad[Codensity[F, ?]] =
    new StackSafeMonad[Codensity[F, ?]] {
      def pure[A](a: A): Codensity[F, A] = Codensity(Monad[F].pure(a))

      def flatMap[A, B](fa: Codensity[F, A])(f: A => Codensity[F, B]): Codensity[F, B] =
        new Codensity[F, B] {
          def apply[C](g: B => F[C]): F[C] = fa(a => f(a)(g))
        }
    }

  type Box[A] = Codensity[Id, A]
}

/** Yoneda f a: forall b. (a -> b) -> f b */
sealed trait Yoneda[F[_], A] {
  /** You can extract an `F`. */
  def apply[B](f: A => B): F[B]

  /** You can recover the `F[A]` even if you forgot it. */
  def run(): F[A] = apply(identity)

  def toCoyoneda: Coyoneda[F, A] = Coyeneda(run)
}

object Yoneda {
  def apply[F[_] : Functor, A](fa: F[A]): Yoneda[F, A] =
    new Yoneda[F, A] {
      def apply[B](f: A => B): F[B] = fa map f
    }

  /** `Yoneda` is a functor even after we forget `F` was one. */
  implicit def functor[F[_]]: Functor[Yoneda[F, ?]] =
    new Functor[Yoneda[F, ?]] {
      /** Allows map fusion without traversing an `F`. */
      def map[A, B](fa: Yoneda[F, A])(f: A => B): Yoneda[F, B] =
        new Yoneda[F, B] {
          def apply[C](g: B => C): F[C] = fa(g compose f)
        }
    }

  type Box[A] = Yoneda[Id, A]
}

/** Coyoneda f a: exists b. (f b, b -> a) -> f a
 * 
 * Yoneda is the cofree functor, while its dual, Coyoneda, is the free functor.
 * */
sealed trait Coyoneda[F[_], A] {
  type B

  val fb: F[B]
  val k: B => A

  def run(implicit functor: Functor[F]): F[A] = fb map k

  def toYoneda(implicit functor: Functor[F]): Yoneda[F, A] = Yoneda(run)
}

object Coyeneda {
  // F doesn't need to be a Functor (yet).
  def apply[F[_], A](fa: F[A]): Coyoneda[F, A] =
    new Coyoneda[F, A] {
      type B = A
      val fb = fa
      val k = identity
    }

  // But Coyeneda is a Functor!
  implicit def functor[F[_]]: Functor[Coyoneda[F, ?]] =
    new Functor[Coyoneda[F, ?]] {
      def map[A, B](fa: Coyoneda[F, A])(f: A => B): Coyoneda[F, B] =
        new Coyoneda[F, B] {
          type B = fa.B
          val fb = fa.fb
          val k = f compose fa.k
        }
    }
}