Skip to content

Instantly share code, notes, and snippets.

@arosien
Created April 12, 2019 17:28
Show Gist options
  • Save arosien/0abf67f56c6730b559aa152bf54d44a1 to your computer and use it in GitHub Desktop.
Save arosien/0abf67f56c6730b559aa152bf54d44a1 to your computer and use it in GitHub Desktop.
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
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment