Skip to content

Latest commit

 

History

History
763 lines (590 loc) · 30.1 KB

Profunctors.md

File metadata and controls

763 lines (590 loc) · 30.1 KB
Raw
classDiagram
   Functor~F[+_]~ <|-- Bifunctor~F[+_,+_]~
   Functor <|-- Bifunctor
   Functor <|-- Profunctor~F[-_,+_]~
   Contravariant~F[-_]~ <|-- Profunctor
   Semicategory~F[-_,+_]~ <|-- Category~F[-_,+_]~
   Category <|-- Arrow~F[-_,+_]~
   Bifunctor <|-- Zivariant~F[-_,+_,+_]~
   Profunctor <|-- Zivariant
   Profunctor <|-- Strong~F[-_,+_]~
   Strong -- Arrow
   Arrow <|-- ArrowApply~F[-_,+_]~
   Arrow <|-- CommutativeArrow~F[-_,+_]~
   Arrow <|-- ArrowLoop~F[-_,+_]~
   Profunctor <|-- Choice~F[-_,+_]~
   Arrow <|-- ArrowZero~F[-_,+_]~
   Arrow <|-- ArrowChoice~F[-_,+_]~
   Choice <|-- ArrowChoice

   class Functor {
     ) map(F[A], A => B): F[B]
   }
   class Contravariant {
     ) contramap(F[A], B => A): F[B]
   }
   class Semicategory {
     ) compose[A,B,C](F[B,C], F[A,B]): F[A,C]
   }
  class Category {
    ) id[A]: F[A,A]
  }
  class Profunctor {
    ) dimap(AA => A, B => BB): P[A,B] => P[AA,BB]
  }
  class Bifunctor {
    ) bimap(A => AA, B => BB): P[A,B] => P[AA,BB]
  }
  class Zivariant {
    ) zimap(AA => A, B => BB, C => CC): P[A,B,C] => P[AA,BB,CC]
  }
  class Strong {
    ) first(P[A,B]): P[(A,C), (B,C)]
  }
  class Choice {
    ) left(P[A,B]): P[Either[A, C], Either[B, C]]
  }
  class Arrow {
    ) arr(A => B): F[A, B]
  }
  class ArrowZero {
    ) zeroArr(): P[A,B]
  }
  class ArrowApply {
    ) app(P[P[B,C],B]): C
  }
  class ArrowApply {
    ) app(P[P[B,C],B]): C
  }
  class ArrowLoop {
    ) loop(P[(B,D), (C,D)]: P[B,C]
  }
Loading

Profunctor

Profunctor abstract over

  • type constructor with two holes P[_,_]
  • operation def dimap(preA: NewA => A, postB: B => NewB): P[A, B] => P[NewA, NewB] that given P[A,B] and two functions
  • apply first preA before first type of P (ast as contravariant functor)
  • apply second postB after second type of P (act as functor)

Alternatively we can define Profunctor not using dimap but using two separate functions:

  • def lmap(f: AA => A): P[A,C] => P[AA,C] = dimap(f,identity[C])
  • def rmap(f: B => BB): P[A,B] => P[A,BB] = dimap(identity[A], f)

Profunctors in Haskell were explored by sifpe at blog A Neighborhood of Infinity in post Profunctors in Haskell Implemented in Haskell: ekmett/profunctors

trait Profunctor[F[_, _]] {
  def dimap[A, B, C, D](fab: F[A, B])(f: C => A)(g: B => D): F[C, D]
}
def lmap[A, B, C](fab: F[A, B])(f: C => A): F[C, B]
def rmap[A, B, C](fab: F[A, B])(f: B => C): F[A, C]
  • Most popular is instance for Function with 1 argument:
trait Profunctor[Function1] {
  def lmap[A,B,C](f: A => B): (B => C) => (A => C) = f andThen
  def rmap[A,B,C](f: B => C): (A => B) => (A => C) = f compose
}

Becasue Profunctors can be used as base to define Arrows therefore there are instances for Arrow like constructions like Kleisli

  • In Category Theory: When we have Category C and D and D' the opposite category to D, then a Profunctor P is a Functor D' x C -> Set We write D -> C In category of types and functions we use only one category, so Profunctor P is C' x C => C

  • Laws Scalaz 7 Cats:

  • if we define Profunctor using dimap:
    • dimap id id == id
def dimapIdentity[A, B](p: P[A, B]): Boolean = {
  //          dimap(id, id)
  // P[A,B] ================> P[A,B]
  dimap(identity[A], identity[B])(p) == p
}
  • dimap (f . g) (h . i) == dimap g h . dimap f i
def dimapComposition[A, B, C, D, E, F](pad: P[A,D], fcb: C => B, fba: B => A, fde: D => E, fef: E => F): Boolean = {
  //          dimap B=>A D=>E
  // P[A,D] ===================> F[B,E]
  val pbe: P[B, E] = dimap(fba, fde)(pad)
  //          dimap C=>B E=>F
  // P[B,E] ====================> P[C,F]
  val l: P[C,F] = dimap(fcb, fef)(pbe)

  val fca: C => A = fba compose fcb
  val fdf: D => F = fef compose fde
  //         dimap C=>A D=> F
  // P[A,D] ===================> P[C,F]
  val r: P[C,F] = dimap(fca, fdf)(pad)
  
  l == r
}

Second law we get for free by parametricity.

  • if specify lmap or rmap
    • lmap id == id
    • rmap id == id
    • lmap (f . g) == lmap g . lmap f
    • rmap (f . g) == rmap f . rmap g

Last two laws we get for free by parametricity.

  • if specify both (in addition to law for dimap and laws for lmap:
    • dimap f g == lmap f . rmap g

Star

Lift Functor into Profunctor "forward"

case class Star[F[_],D,C](runStar: D => F[C])

If F is a Functor then Star[F, ?, ?] is a Profunctor:

def profunctor[F[_]](implicit FF: Functor[F]): Profunctor[Star[F, ?,?]] = new Profunctor[Star[F, ?, ?]] {
  def dimap[X, Y, Z, W](ab: X => Y, cd: Z => W): Star[F, Y, Z] => Star[F, X, W] = bfc =>
    Star[F,X, W]{ x =>
      val f: Y => F[Z] = bfc.runStar
      val fz: F[Z] = f(ab(x))
      FF.map(fz)(cd)
    }
}

CoStar

Lift Functor into Profunctor "backwards"

case class Costar[F[_],D,C](runCostar: F[D] => C)

If F is a Functor then Costar[F, ?, ?] is a Profunctor

def profunctor[F[_]](FF: Functor[F]): Profunctor[Costar[F, ?, ?]] = new Profunctor[Costar[F, ?, ?]] {
  def dimap[A, B, C, D](ab: A => B, cd: C => D): Costar[F, B, C] => Costar[F, A, D] = fbc =>
    Costar{ fa =>
      val v: F[B] = FF.map(fa)(ab)
      val c: C = fbc.runCostar(v)
      cd(c)
    }
}

Strong Profunctor

Profunctor with additional method first that lift profunctor so it can run on first element of tuple.

For Profunctor of functions from A to B this operation just apply function to first element of tuple.

trait StrongProfunctor[P[_, _]] extends Profunctor[P] {
  def first[X,Y,Z](pab: P[X, Y]): P[(X, Z), (Y, Z)]
}
  • Laws Haskell Scalaz 7 Cats
    1. first == dimap(swap, swap) andThen second
    2. lmap(_.1) == rmap(_.1) andThen first
    3. lmap(second f) andThen first == rmap(second f) andThen first
    4. first . first ≡ dimap assoc unassoc . first
    5. second ≡ dimap swap swap . first
    6. lmap snd ≡ rmap snd . second
    7. lmap (first f) . second ≡ rmap (first f) . second
    8. second . second ≡ dimap unassoc assoc . second

where

assoc ((a,b),c) = (a,(b,c))
unassoc (a,(b,c)) = ((a,b),c)

In Notions of Computation as Monoids by Exequiel Rivas and Mauro Jaskelioff in 7.1 there are following laws:

  1. dimap identity pi (first a) = dimap pi id a
  2. first (first a) = dimap alphaInv alpha (first a)
  3. dimap (id × f) id (first a) = dimap id (id × f) (first a)
  • Derived methods:
def second[X,Y,Z](pab: P[X, Y]): P[(Z, X), (Z, Y)]
def uncurryStrong[P[_,_],A,B,C](pa: P[A, B => C])(S: Strong[P]): P[(A,B),C]

In Purescript implementation of Strong there are some more helper methods that use Category constraint for P.

  • Most common instance is Function with one argument:
val Function1Strong = new Strong[Function1] with Function1Profunctor {
  def first[X, Y, Z](f: Function1[X, Y]): Function1[(X,Z), (Y, Z)] = { case (x,z) => (f(x), z) }
}

it is possible to define instance for Kleisli arrow

Tambara

trait Tambara[P[_,_],A,B]{
  def runTambara[C]: P[(A,C),(B,C)]
}

Tambara is a Profunctor:

trait Profunctor[Tambara[P, ?, ?]] {
  def PP: Profunctor[P]

  def dimap[X, Y, Z, W](f: X => Y, g: Z => W): Tambara[P, Y, Z] => Tambara[P, X, W] = (tp : Tambara[P, Y, Z]) => new Tambara[P, X, W]{
   
    def runTambara[C]: P[(X, C), (W, C)] = {
      val fp: P[(Y,C),(Z,C)] => P[(X, C), (W, C)] = PP.dimap(
        Function1Strong.first[X, Y, C](f),
        Function1Strong.first[Z, W, C](g)
      )
      val p: P[(Y,C),(Z,C)] = tp.runTambara[C]
      fp(p)
    }
  }
}

It is also FunctorProfunctor:

def promap[P[_, _], Q[_, _]](f: DinaturalTransformation[P, Q])(implicit PP: Profunctor[P]): DinaturalTransformation[Lambda[(A,B) => Tambara[P, A, B]], Lambda[(A,B) => Tambara[Q, A, B]]] = {
  new DinaturalTransformation[Lambda[(A,B) => Tambara[P, A, B]], Lambda[(A,B) => Tambara[Q, A, B]]] {
    def dinat[X, Y](ppp: Tambara[P, X, Y]): Tambara[Q, X, Y] = new Tambara[Q, X, Y] {
      def runTambara[C]: Q[(X, C), (Y, C)] = {
        val p: P[(X,C), (Y,C)] = ppp.runTambara
        f.dinat[(X,C), (Y,C)](ppp.runTambara)
      }
    }
  }
}

Profunctor Costrong

trait Costrong[F[_,_]] extends Profunctor[F] {
  def unfirst[A,B,D](fa: F[(A,D), (B, D)]): F[A,B]
  def unsecond[A,B,D](fa: F[(D,A),(D,B)]): F[A,B]
}

Choice Profunctor

Profunctor with additional method left that wrap both types inside Either.

trait ProChoice[P[_, _]] extends Profunctor[P] {
  def left[A,B,C](pab: P[A, B]):  P[Either[A, C], Either[B, C]]
}
  • derived method
def right[A,B,C](pab: P[A, B]): P[Either[C, A], Either[C, B]]

Extranatural Transformation

trait ExtranaturalTransformation[P[_,_],Q[_,_]]{
  def exnat[A,B](p: P[A,B]): Q[A,B]
}

Profunctor Functor

Functor (endofunctor) between two Profunctors.

It is different than regualar Functor: Functor lifts regular function to function working on type constructor: def map[A, B](f: A => B): F[A] => F[B] Profunctor lifts two regular functions to work on type constructor with two holed.

And ProfunctorFunctor lifts dinatural transformation of two Profunctors P[,] => Q[,]

operates on type constructor with one hole (F[A] => F[B]) and ProfunctorFunctor and ProfunctorFunctor map P[A,B] => Q[A,B]

in Scala 2.12 we cannot express type constructor that have hole with shape that is not sepcified)

trait ProfunctorFunctor[T[_]] {
  def promap[P[_,_], Q[_,_]](dt: DinaturalTransformation[P,Q])(implicit PP: Profunctor[P]): DinaturalTransformation[Lambda[(A,B) => T[P[A,B]]], Lambda[(A,B) => T[Q[A,B]]]]
}

Profunctor Monad

trait ProfunctorMonad[T[_]] extends ProfunctorFunctor[T] {
  def proreturn[P[_,_]](implicit P: Profunctor[P]): DinaturalTransformation[P, Lambda[(A,B) => T[P[A,B]]]]
  def projoin[P[_,_]](implicit P: Profunctor[P]): DinaturalTransformation[Lambda[(A,B) => T[T[P[A,B]]]], Lambda[(A,B) => T[P[A,B]]]]
}
  • Laws:
    • promap f . proreturn == proreturn . f
    • projoin . proreturn == id
    • projoin . promap proreturn == id
    • projoin . projoin == projoin . promap projoin

Profunctor Comonad

trait ProfunctorComonad[T[_]] extends ProfunctorFunctor[T] {
  def proextract[P[_,_]](implicit P: Profunctor[P]): DinaturalTransformation[Lambda[(A,B) => T[P[A,B]]], P]
  def produplicate[P[_,_]](implicit P: Profunctor[P]): DinaturalTransformation[Lambda[(A,B) => T[P[A,B]]], Lambda[(A,B) => T[T[P[A,B]]]]]
}
  • Laws
    • proextract . promap f == f . proextract
    • proextract . produplicate == id
    • promap proextract . produplicate == id
    • produplicate . produplicate == promap produplicate . produplicate

Profunctor Yoneda

trait ProfunctorYoneda[P[_,_],A,B] {
  def runYoneda[X,Y](f: X => A, g: B => Y): P[X,Y]
}

is a Profunctor for free, because we can define:

def dimap[AA, BB](l: AA => A, r: B => BB): ProfunctorYoneda[P, AA, BB] = new ProfunctorYoneda[P, AA, BB] {
  def runYoneda[X, Y](l2: X => AA, r2: BB => Y): P[X, Y] = {
    val f1: X => A = l compose l2
    val f2: B => Y = r2 compose r
    self.runYoneda(f1, f2)
  }
}

Profunctor CoYoneda

trait ProfunctorCoyoneda[P[_,_],A,B] {
  type X
  type Y
  def f1: A => X
  def f2: Y => B
  def pxy: P[X,Y]
}

helper constructor:

def apply[XX,YY,P[_,_],A,B](ax: A => XX, yb: YY => B, p: P[XX,YY]): ProfunctorCoyoneda[P,A,B] = new ProfunctorCoyoneda[P,A,B] {
  type X = XX
  type Y = YY
  def f1: A => X = ax
  def f2: Y => B = yb
  def pxy: P[X,Y] = p
}

ProfunctorCoyoneda is a Profunctor for free:

def dimap[C, W](l: C => A, r: B => W): ProfunctorCoyoneda[P, C, W] =
  ProfunctorCoyoneda[X, Y, P, C, W](f1 compose l, r compose f2, pxy)

Profunctor Ran

Profunctor Codensity

Profunctor Adjunction

Profunctor Rep

  • TODO Corepresentable, Corep, Prep, Coprep

  • Implementations: Haskell

Procompose

In general Profunctors should have straightforward way to compose them as we have the same category in definition. But to be faithfull with Category Theory definition, Profunctor Composition is defined using exitential types:

trait Procompose[P[_,_],Q[_,_],D,C] {
  type X
  val p: P[X,C]
  val q: Q[D,X]
}

ProductProfunctor

A generalization of Profunctor by adding Applicative superpowers to output. Documentation of tomjaguarpaw/product-profunctors on Hackage is excelent.

class Profunctor p => ProductProfunctor p where
  purePP :: b -> p a b
  (****) :: p a (b -> c) -> p a b -> p a c
  empty  :: p () ()
  (***!) :: p a b -> p a' b' -> p (a, a') (b, b')

(***$) :: ProductProfunctor p => (b -> c) -> p a b -> p a c
  • utility methods from p0 to p62
p3 :: forall p a0 a1 a2 b0 b1 b2. ProductProfunctor p => (p a0 b0, p a1 b1, p a2 b2) -> p (a0, a1, a2) (b0, b1, b2)

from to pT1 to pT62

pT3 :: forall p a0 a1 a2 b0 b1 b2. ProductProfunctor p => T3 (p a0 b0) (p a1 b1) (p a2 b2) -> p (T3 a0 a1 a2) (T3 b0 b1 b2)

SumProfunctor

class Profunctor p => SumProfunctor p where
  (+++!) :: p a b -> p a' b' -> p (Either a a') (Either b b')

list :: (ProductProfunctor p, SumProfunctor p) => p a b -> p [a] [b]

ProfunctorEnd

class Profunctor p => ProfunctorEnd p where
  end :: p a a

instance ProfunctorEnd (->) where
  end = id

Arrows

Category

Abstraction for operations that can be composed and that provide no-op (id)

trait Category[F[_, _]] {
  def id[A]: F[A, A]
  def compose[A, B, C](f: F[B, C], g: F[A, B]): F[A, C]
}

that satisfy certain conditions.

def compositivityLaw[A,B,C,D](g: M[B,C], f: M[A,B], h:M[C,D]): Boolean = {
  val gf: M[A, C] = compose(g)(f)
  val v2: M[A, D] = compose(h)(gf)

  val hg: M[B, D] = compose(h)(g)
  val w2: M[A, D] = compose(hg)(f)

  v2 == w2
}
  • identity f.compose(id) == id.compose(f) == f
def leftIdentityLaw[A,B](fa: M[A,B]): Boolean = {
  compose(id[B])(fa) == fa
}

def rightIdentityLaw[A,B](fa: M[A,B]): Boolean = {
  compose(fa)(id[A]) == fa
}
  • Resources
    • (Category Theory) Category Theory 1.2: What is a category? - Bartosz Milewski (video)
    • Hask is not a category - Andrej Bauer (blog)

Category of types and functions

Types in given programming language like Scala or Haskell with one argument pure functions form a category - called Scala or Hask respectively. (Because in Haskell functions are automatically curried - there is no requirements for 1 argument.)

trait Function1Cat extends Category[Function1] {
  def id[A]: A => A = identity[A]
  def compose[A, B, C](f: B => C)(g: A => B): A => C = g andThen f
}

Functor category

Functor category is a category where objects are functors and morphisms are natural transformations. Provided definition of category does not allow to express this. We could encode this in following way:

object CategoryKInstances {
  val functorCategory: CategoryK[~>] = new CategoryK[~>] {
    def id[F[_]]: F~>F = new IdNat[F]
    def compose[A[_], B[_], C[_]](f: B ~> C)(g: A ~> B): A ~> C = VerticalCompositionNat(g,f)
  }
}

trait CategoryK[Morphism[ _[_], _[_] ]] {
  def id[A[_]]: Morphism[A,A]
  def compose[A[_],B[_],C[_]](f: Morphism[B,C])(g: Morphism[A,B]): Morphism[A,C]
}

trait ~>[F[_], G[_]] {
  def apply[A](fa: F[A]): G[A]
}

case class VerticalCompositionNat[F[_],G[_],H[_]](f: F~>G, g: G~>H) extends ~>[F,H] {
  def apply[A](fa: F[A]): H[A] = g(f(fa))
}

case class IdNat[F[_]]() extends ~>[F,F] {
  def apply[A](fa: F[A]): F[A] = fa
}

Implementation in statebox/idris-ct

Arrow

CommutativeArrow

Arrow Choice

Arrow Apply, Arrow Monad

Arrow Loop

Arrow Zero

Kleisli

case class Kleisli[F[_],A,B](run: A => F[B])

Cokleisli

case class CoKleisli[F[_],A,B](run: F[A] => B)
  • Cats

BiArrow

  • Resources:
    • There and back again: arrows for invertible programming - Artem Alimarine , Sjaak Smetsers , Arjen Weelden , Marko Eekelen , Rinus Plasmeijer (paper)
    • (Haskell) BiArrow

BiKleisli

Dinatural Transformation

Dinatural Transformation is a function that change one Profunctor P into another one Q without modifying the content. It is equivalent to Natural Transformation between two Functors (but for Profunctors).

trait DinaturalTransformation[P[_,_],Q[_,_]]{
  def dinat[A](p: P[A,A]): Q[A,A]
}

Ends & Coends

Ends can be seen as infinite product. End corresponds to forall so polymorphic function:

// P is Profunctor

trait End[P[_,_]] {
  def run[A]: P[A,A]
}

Coend can be seen as infinite coproduct (sum). Coends corresponds to exists

data Coend p = forall x. Coend p x x