Profunctors.md

Don't Fear the Profunctor Optics (Part 2/3)

PREVIOUSLY: Optics, Concretely

Today it's the turn of profunctors. We'll start with a very brief introduction to covariant and contravariant functors. Then, we'll see the most relevant members of the profunctor family. Particularly, we'll show their representation as typeclasses (along with their associated laws and several instances) and a visual representation where profunctors are seen as boxes that take inputs and produce outputs. Here we go!

Profunctors as Generalized Functions

(Covariant) Functors arise everywhere! When we put our programmer's glasses on, we can view them as containers that can be mapped over with fmap:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Not surprisingly, functions are functors, when they're parameterized on their result type:

instance Functor ((->) r) where
  fmap f g = f . g

Contravariant functors are pretty much like functors, but they require a reversed arrow to map the container in the expected direction:

class Contravariant f where
  cmap :: (b -> a) -> f a -> f b

Functions are also contravariant, this time on their first type parameter:

newtype CReader r a = CReader (a -> r)

instance Contravariant (CReader r) where
  cmap f (CReader g) = CReader (g . f)

Now, we should be ready to approach profunctors. For each member of the profunctor family, we'll show its typeclass and associated laws, along with a (->) instance. Then, we'll provide an informal explanation which is supported by our profunctor diagrams.

Profunctor

Profunctors are sort of functors which are contravariant on their first argument and covariant on their second one. Thereby, its abstract method dimap takes two functions as input:

class Profunctor p where
  dimap :: (a' -> a) -> (b -> b') -> p a b -> p a' b'

  lmap :: (a' -> a) -> p a b -> p a' b
  lmap f = dimap f id
  rmap :: (b -> b') -> p a b -> p a b'
  rmap f = dimap id f

lmap and rmap are utilities to map either the covariant or the contravariant type parameter. Therefore, they correspond with contravariant's cmap and functor's fmap, respectively. As every interesting typeclass, profunctors do obey some laws:

dimap id id = id
dimap (f' . f) (g . g') = dimap f g · dimap f' g'

As expected, functions do fit perfectly as instances of this typeclass:

instance Profunctor (->) where
  dimap f g h = g . h . f

Explanation

Profunctors are best understood as generalizations of functions. As a consequence, we can see them as boxes that take an input and provide an output. Thereby, dimap just adapts inputs and outputs to conform new boxes. Given this intuition, I noticed that drawing diagrams could be helpful to understand the profunctor family. Soon, I realized that these new diagrams were quite similar to the ones provided by Hughes for arrows. In fact, there are strong connections among them. From now on, we'll be using them to provide a visual perspective of profunctors:

Here, h :: p a b is our original profunctor box. For being a profunctor we know that it can be extended with dimap, using plain functions f :: a' -> a and g :: b -> b', represented as circles. Once we apply dimap a surrounding profunctor box is generated, which is able to take a's as input and produce b's as output.

These diagrams also help to better understand profunctor laws. This picture represent the first of them dimap id id = id:

Basically, it says that we can replace an id function with a raw cable. Then, the surrounding profunctor box would become redundant. On the other hand, the second law dimap (f' . f) (g . g') = dimap f g · dimap f' g' is represented as follows:

It tells us that we can split a dimap which takes composed functions into a composition of dimaps where each takes the corresponding uncomposed functions.

Cartesian

Following down the profunctor family, we find Cartesian:

class Profunctor p => Cartesian p where
  first  :: p a b -> p (a, c) (b, c)
  second :: p a b -> p (c, a) (c, b)

These are the laws associated to this typeclass (skipping the counterparts for second):

dimap runit runit' h = first h
dimap assoc assoc' (first (first h)) = first h
-- where
runit  :: (a, ()) -> a
runit' :: a -> (a, ())
assoc  :: (a, (b, c)) -> ((a, b), c)
assoc' :: ((a, b), c) -> (a, (b, c))

The function instance for cartesian is straightforward:

instance Cartesian (->) where
  first  f (a, c) = (f a,   c)
  second f (c, a) = (  c, f a)

Explanation

Again, this typeclass contains methods that turn certain box p a b into new ones. Particularly, these methods make our original box coexist with an additional input c, either in the first or second position. Using our diagram representation, we get:

As usual, we start from a simple h :: p a b. Once first is applied we can see how c input passes through, while a is turned into a b, using the original box h for the task. The most characteristic feature of the resulting box is that it takes two inputs and produce two outputs.

When we draw the first cartesian law dimap runit runit' h = first h, we get the next diagram:

This law is claiming that first should pass first input through h while second input should be preserved in the output as is. That intuition turns out to be implicit in our diagram representation. The second law dimap assoc assoc' (first (first h)) = first h is shown graphically in this image:

This representation seems more complex, but in essence, it states that nesting firsts doesn't break previous law. This is implicit in the diagram as well, where b and c simply pass-through, regardless of the nested boxes in the upper case.

Cocartesian

Next, there is Cocartesian, whose primitives are shown in the following typeclass:

class Profunctor p => Cocartesian p where
  left  :: p a b -> p (Either a c) (Either b c)
  right :: p a b -> p (Either c a) (Either c b)

Its laws are these ones (ignoring right counterparts):

dimap rzero rzero' h = left h
dimap coassoc' coassoc (left (left h)) = left h
--where
rzero    :: Either a Void -> a
rzero'   :: a -> Either a Void
coassoc  :: Either a (Either b c) -> Either (Either a b) c
coassoc' :: Either (Either a b) c -> Either a (Either b c)

And here it's the function instance:

instance Cocartesian (->) where
  left  f = either (Left . f) Right
  right f = either Left (Right . f)

Explanation

Indeed, this typeclass is very similar to Cartesian, but the resulting box deals with sum types (Either) instead of product types. What does it mean from our diagram perspective? It means that inputs are exclusive and only one of them will be active in a particular time. The input itself determines which path should be active. The corresponding diagram is shown in the next picture:

As one could see, left turns the original h :: p a b into a box typed p (Either a c) (Either b c). Internally, when an a matches, the switch takes the upper path, where h delivers a b as output. Otherwise, when c matches, the lower path will be activated, and the value passes through as is. Notice that switches in both extremes must be coordinated to make things work, either activating the upper or the lower path. On the other hand, right is like left where paths are swapped. We left diagram representation of laws as an exercise for the reader.

Monoidal

Finally, the last profunctor that will be covered is Monoidal. As usual, here's the associated typeclass:

class Profunctor p => Monoidal p where
  par   :: p a b -> p c d -> p (a, c) (b, d)
  empty :: p () ()

Monoidal laws are encoded as follows:

dimap assoc assoc' (par (par h j) k) = par h (par j k)
dimap runit runit' h = par h empty
dimap lunit lunit' h = par empty h
-- where
lunit  :: ((), a) -> a
lunit' :: a -> ((), a)

Instantiating this typeclass for function is trivial:

instance Monoidal (->) where
  par f g (a, c) = (f a, g c)
  empty = id

Explanation

Now, we'll focus on par. It receives a pair of boxes, p a b and p c d, and it builds a new box typed p (a, c) (b, d). Given this signature, it's easy to figure out what's going on in the shadows. It's shown in the next diagram:

The resulting box make both arguments (h and j) coexist, by connecting them in parallel (therefore the name par).

Beyond Functions

So far, we've been instantiating profunctor typeclasses with plain functions. However, as we said before, profunctors do generalize functions. What other kind of things (beyond functions) can be represented with them?

Well, there is UpStar, which is pretty similar to a function, though returning a fancy type:

newtype UpStar f a b = UpStar { runUpStar :: a -> f b }

We can provide instances for many profunctor typeclasses:

instance Functor f => Profunctor (UpStar f) where
  dimap f g (UpStar h) = UpStar (fmap g . h . f)

instance Functor f => Cartesian (UpStar f) where
  first (UpStar f)  = UpStar (\(a, c) -> fmap (,c) (f a))
  second (UpStar f) = UpStar (\(c, a) -> fmap (c,) (f a))

-- XXX: `Pointed` should be good enough, but it lives in external lib
instance Applicative f => Cocartesian (UpStar f) where
  left  (UpStar f) = UpStar (either (fmap Left . f) (fmap Right . pure))
  right (UpStar f) = UpStar (either (fmap Left . pure) (fmap Right . f))

instance Applicative f => Monoidal (UpStar f) where
  par (UpStar f) (UpStar g) = UpStar (\(a, b) -> (,) <$> f a <*> g b)
  empty = UpStar pure

Notice that we need some evidences on f to be able to implement such instances, particularly Functor or Applicative. We encourage the reader to instantiate these instances also for DownStar (where the fanciness is in the parameter type) as an exercise:

newtype DownStar f a b = DownStar { runDownStar :: f a -> b }

(You may not able to instantiate all three classes for DownStar. If so, try to reason about why certain class cannot be instantiated.)

Take Tagged as another example:

newtype Tagged a b = Tagged { unTagged :: b }

This is just a wrapper for bs, having a as a phantom input type. In fact, it represents somehow a constant function. You can provide instances for many profunctor typeclasses with it:

instance Profunctor Tagged where
  dimap f g (Tagged b) = Tagged (g b)

instance Cocartesian Tagged where
  left  (Tagged b) = Tagged (Left b)
  right (Tagged b) = Tagged (Right b)

instance Monoidal Tagged where
  par (Tagged b) (Tagged d) = Tagged (b, d)
  empty = Tagged ()

Try to reason about the impossibility of determining an instance for Cartesian as an exercise.

We've chosen DownStar and Tagged because we'll use them in the next part of this series. However, you should know that there are other awesome instances for profunctors out there. As you see, profunctors also arise everywhere!

NEXT: Profunctor Optics