Skip to content

Latest commit

 

History

History
432 lines (348 loc) · 18 KB

KanExtensions.md

File metadata and controls

432 lines (348 loc) · 18 KB
Raw

(Co)Yoneda & (Co)Density & Kan Extensions

classDiagram
   Ran~G[_], H[_], A~ <|-- Yoneda~H[_], A~
   Lan~G[_], H[_], A~ <|-- CoYoneda~H[_], A~
   Ran <|-- Codensity~G[_], A~
   Lan <|-- Density~G[_], A~

  class Ran {
    // Right Kan Extension
    ) run[B](A => G[B]): H[B]
  }
  class Yoneda {
    ) run[B](A => B): H[R]
  }
  class Codensity {
    ) run[B](A => G[B]): G[B]
  }
  class Lan {
    // Left Kan Extension
    fz: H[Z]
    run: G[Z] => A
  }
  class CoYoneda {
    fz: H[Z]
    run: Z => A
  }
  class Density {
    fz: G[Z]
    run: G[Z] => A
  }
  class Day~G[_], H[_], A~ {
    // Day convolution
    gb: G[Z]
    hb: H[X]
    ) run: (Z,X) => A
  }
Loading

Yoneda

Construction that abstract over type constructor and allow to efficiently stack computations.

In Category Theory

Yoneda Lemma states that: [C,Set](C(a,-),F) ~ F a natural transformation between Hom(a,-) and functor F: C -> Set is isomorphic to value of Functor F on a F a.

In Haskell this can be expressed as

f a  ~ forall x. (a -> x) -> f x

In Scala we ca define:

abstract class Yo[F[+_], A] {
  def runYo(): Reader[A, *] ~> F[*]
}

type YonedaLemma[F[+_], A] = Yo[F, A] ~ F[A]
def yonedaLemma[F[+_], A](implicit FF: Functor[F]): YonedaLemma[F, A] =
  new YonedaLemma[F, A] {
    def to: F[A] => Yo[F, A] = fa =>
      new Yo[F, A] {
        def runYo(): (A => *) ~> F =
          λ[(A => *) ~> F](atox => FF.map(fa)(atox))
      }

    def from: Yo[F, A] => F[A] =
      (fa: Yo[F, A]) => {
        val raf: Reader[A, *] ~> F = fa.runYo()
        raf.apply(identity[A])
      }
  }

where:

type Reader[-R, +A] = R => A

trait ~[A, B] {
  def to: B => A
  def from: A => B
}

In practice of FP following data structure is used:

trait Yoneda[F[_], A] {
  def run[X](f: A => X): F[X]
}

we need Functor instance for F to create instance of Yoneda for F

def liftYoneda[F[_], A](fa: F[A])(implicit FunctorF: Functor[F]): Yoneda[F, A] =
  new Yoneda[F, A] {
    def run[X2](f: A => X2): F[X2] = FunctorF.map(fa)(f)
  }

yet we don't need the fact that F is a Functor to go back to F

def lowerYoneda[F[_], A](y: Yoneda[F, A]): F[A] = y.run(identity[A])

We can define Functor instance, without any requirement on F:

def yonedaFunctor[F[_]]: Functor[Yoneda[F, *]] =
  new Functor[Yoneda[F, *]] {
    def map[A, B](fa: Yoneda[F, A])(f: A => B): Yoneda[F, B] =
      new Yoneda[F, B] {
        def run[C](f2: B => C): F[C] = fa.run(f andThen f2)
      }
  }

Coyoneda

Rúnar in Free Monads and the Yoneda Lemma describes this type as a proof that: "if we have a type B, a function of type (B => A) for some type A, and a value of type F[B] for some functor F, then we certainly have a value of type F[A]"

This result from Category Theory allows us to perform Coyoneda Trick:

If we have following type:

trait Coyoneda[F[_], A] {
  type B
  def f: B => A
  def fb: F[B]
}

then type constructor F can be lifted to Coyoneda

def liftCoyoneda[F[_], A](fa: F[A]): Coyoneda[F, A]

we can map over lifted constructor F, without any requirements on F. So Coyoneda is a Free Functor:

implicit def coyoFunctor[F[_]]: Functor[Coyoneda[F, ?]] = new Functor[Coyoneda[F, ?]] {
  def map[A, AA](fa: Coyoneda[F, A])(ff: A => AA): Coyoneda[F, AA] = new Coyoneda[F, AA] {
    type B = fa.B
    def f: B => AA = fa.f andThen ff
    def fb: F[B] = fa.fb
  }
}

We even can change the oryginal type of F

def hoistCoyoneda[F[_], G[_], A, C](fab : NaturalTransf[F,G])(coyo: Coyoneda[F, A]): Coyoneda[G, A] =
  new Coyoneda[G, A] {
    type B = coyo.B
    def f: B => A = coyo.f
    def fb: G[B] = fab(coyo.fb)
  }

Finally to get back from Coyoneda fantazy land to reality of F, we need a proof that it is a Functor:

def lowerCoyoneda(implicit fun: Functor[F]): F[A]

  • Implementations: calaz 7, Haskell, nLab

  • Resources

    • loop/recur Coyoneda (video)
    • Free Monads and the Yoneda Lemma - Rúnar Bjarnason (blog post)
    • (Scala & Haskell) How Haskell is Changing my Brain, Yay Yoneda - Alissa Pajer (video)
    • (Haskell) Reverse Engineering Machines with the Yoneda Lemma - Dan Piponi: (blog post)
    • (Haskell) Free Monads for Less (Part 2 of 3): Yoneda - Edward Kmett (blog post)

Right Kan extension

trait Ran[G[_], H[_], A] {
  def runRan[B](f: A => G[B]): H[B]
}
def ranFunctor[G[_], H[_]]: Functor[Ran[G, H, ?]] =
    new Functor[Ran[G, H, ?]] {

      def map[A, B](fa: Ran[G, H, A])(f: A => B): Ran[G, H, B] =
        new Ran[G, H, B] {
          def runRan[C](f2: B => G[C]): H[C] =
            fa.runRan(f andThen f2)
        }
    }
  • We can define Monad for Ran, without any requirements on G, H. Monad generated by Ran is Codensity.
def codensityMonad[F[_], A](ran: Ran[F, F, A]): Codensity[F, A] =
  new Codensity[F, A] {
    def run[B](f: A => F[B]): F[B] = ran.runRan(f)
  }

Left Kan Extension

trait Lan[F[_], H[_], A] {
  type B
  val hb: H[B]
  def f: F[B] => A
}

Scalaz, Haskell, Purescript, Agda, nLab

  • we can define Functor for it
def lanFunctor[F[_], H[_]]: Functor[Lan[F, H, ?]] = new Functor[Lan[F, H, ?]]() {
  def map[A, X](x: Lan[F, H, A])(fax: A => X): Lan[F, H, X] = {
    new Lan[F, H, X] {
      type B = x.B
      val hb: H[B] = x.hb
      def f: F[B] => X = x.f andThen fax
    }
  }
}

Density Comonad

Density is a Comonad that is simpler that Left Kan Extension. More precisely it is comonad formed by left Kan extension of a Functor along itself.)

trait Density[F[_], Y] { self =>
  type X
  val fb: F[X]
  def f: F[X] => Y
  
  def densityToLan: Lan[F,F,Y] = new Lan[F,F,Y] {
   type B = X
   val hb: F[B] = fb
   def f: F[B] => Y = self.f
  }
}

object Density {
  def apply[F[_], A, B](kba: F[B] => A, kb: F[B]): Density[F, A] = new Density[F, A] {
    type X = B
    val fb: F[X] = kb
    def f: F[X] => A = kba
  }
}

Scalaz PR, Purescript, Haskell

Density form a Functor without any conditions on F, so it is a Free Functor. Similar like Lan.

def functorInstance[K[_]]: Functor[Density[K, ?]] = new Functor[Density[K, ?]] {
  def map[A, B](x: Density[K, A])(fab: A => B): Density[K, B] = Density[K,B,x.X](x.f andThen fab, x.fb)
}

Density is a Comonad without any conditions of F, so it is a Free Comonad.

def comonadInstance[K[_]]: Comonad[Density[K, ?]] = new Comonad[Density[K, ?]] {
  def extract[A](w: Density[K, A]): A = w.f(w.fb)
  def duplicate[A](wa: Density[K, A]): Density[K, Density[K, A]] =
    Density[K, Density[K, A], wa.X](kx => Density[K, A, wa.X](wa.f, kx), wa.fb)
  def map[A, B](x: Density[K, A])(f: A => B): Density[K, B] = x.map(f)
}

Codensity

Interface with flatMap'ish method:

trait Codensity[F[_], A] {
  def run[B](f: A => F[B]): F[B]
}

It gives us monad (without any requirement on F):

implicit def codensityMonad[G[_]]: Monad[Codensity[G, ?]] =
  new Monad[Codensity[G, ?]] {
    def map[A, B](fa: Codensity[G, A])(f: A => B): Codensity[G, B] =
      new Codensity[G, B] {
        def run[C](f2: B => G[C]): G[C] = fa.run(f andThen f2)
      }

    def unit[A](a: A): Codensity[G, A] =
      new Codensity[G, A] {
        def run[B](f: A => G[B]): G[B] = f(a)
      }

    def flatMap[A, B](c: Codensity[G, A])(f: A => Codensity[G, B]): Codensity[G, B] =
      new Codensity[G, B] {
        def run[C](f2: B => G[C]): G[C] = c.run(a => f(a).run(f2))
      }
  }

Cayley representations

"The Cayley representation theorem (CRT): every group is isomorphic to a group of permutations" Can be extended to monoids and defined monoidal category of endofunctor

In FP the CRT is optimisation by change of representation:

  • CRT for List monoid - difference lists
  • CRT for monads - Codensity monad
  • CRT for applicatives - NoCaM 5.4
  • CRT for arrows - ???

Resources:

  • Notions of Computation as Monoids (extended version) - Exequiel Rivas, Mauro Jaskelioff (paper)

Difference lists

  • List with concatenation and empty list is monoid. W optimize list concatenation (that is slow) by representing list as function (difference list):
type Elist[A] = List[A] => List[A]

EList is isomorphic to List:

def rep[A](xs: List[A]): Elist[A] = ys => xs ++ ys
def abs[A](xs: Elist[A]): List[A] = xs(Nil)

We can concatenate EList's efficiently and at the end get to the List back.

  • Cayley Theorem can be define for general Monoid:
trait CayleyTheoremForMonoid[M[_]] extends MonoidK[M] {
  type MonoidEndomorphism[A] = M[A] => M[A]
  def rep[A](xs: M[A]): MonoidEndomorphism[A] = ys => combineK(xs, ys)
  def abs[A](xs: MonoidEndomorphism[A]): M[A] = xs(empty)
}

Resources:

  • (Haskell) Using Difference Lists - geophf blog post
  • (Haskell) keepEquals with Difference Lists - geophf blog post
  • (Haskell) A novel representation of lists and its application to the function "reverse" - John Hughes

Double Cayley Representation

"optimises both left-nested sums and left-nested products"

Resources:

  • A Unified View of Monadic and Applicative Non-determinism - Exequiel Rivas, Mauro Jaskeliof, Tom Schrijvers (paper)