2017-09-21 15:05:04 +03:00
|
|
|
# Don't Fear the Profunctor Optics (Part 2/3)
|
|
|
|
|
|
|
|
PREVIOUSLY: [Optics, Concretely](Optics.md)
|
|
|
|
|
|
|
|
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,
|
2017-09-25 16:07:31 +03:00
|
|
|
we can view them [as
|
|
|
|
containers](https://bartoszmilewski.com/2014/01/14/functors-are-containers/)
|
|
|
|
that can be mapped over with `fmap`:
|
2017-09-21 15:05:04 +03:00
|
|
|
|
|
|
|
```haskell
|
|
|
|
class Functor f where
|
|
|
|
fmap :: (a -> b) -> f a -> f b
|
|
|
|
```
|
|
|
|
|
|
|
|
Not surprisingly, functions are functors, when they're parameterized on their
|
|
|
|
result type:
|
|
|
|
|
|
|
|
```haskell
|
|
|
|
instance Functor ((->) r) where
|
2017-10-07 09:08:57 +03:00
|
|
|
fmap f g = f . g
|
2017-09-21 15:05:04 +03:00
|
|
|
```
|
|
|
|
|
|
|
|
Contravariant functors are pretty much like functors, but they require a
|
|
|
|
reversed arrow to map the container in the expected direction:
|
|
|
|
|
|
|
|
```haskell
|
|
|
|
class Contravariant f where
|
|
|
|
cmap :: (b -> a) -> f a -> f b
|
|
|
|
```
|
|
|
|
|
|
|
|
Functions are also contravariant, this time on their first type parameter:
|
|
|
|
|
|
|
|
```haskell
|
|
|
|
newtype CReader r a = CReader (a -> r)
|
|
|
|
|
|
|
|
instance Contravariant (CReader r) where
|
|
|
|
cmap f (CReader g) = CReader (g . f)
|
|
|
|
```
|
|
|
|
|
2017-09-25 16:07:31 +03:00
|
|
|
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.
|
2017-09-21 15:05:04 +03:00
|
|
|
|
|
|
|
### 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:
|
|
|
|
|
|
|
|
```haskell
|
|
|
|
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
|
2017-09-25 16:07:31 +03:00
|
|
|
type parameter. Therefore, they correspond with contravariant's `cmap` and
|
|
|
|
functor's `fmap`, respectively. As every interesting typeclass, profunctors do
|
|
|
|
obey some laws:
|
2017-09-21 15:05:04 +03:00
|
|
|
|
|
|
|
```haskell
|
|
|
|
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:
|
|
|
|
|
|
|
|
```haskell
|
|
|
|
instance Profunctor (->) where
|
|
|
|
dimap f g h = g . h . f
|
|
|
|
```
|
|
|
|
|
2017-09-25 16:07:31 +03:00
|
|
|
#### Explanation
|
|
|
|
|
|
|
|
Profunctors are best understood as generalizations of functions. As a
|
2017-09-21 15:05:04 +03:00
|
|
|
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](https://www.haskell.org/arrows/). In
|
2017-09-25 16:07:31 +03:00
|
|
|
fact, there are [strong
|
2017-09-21 15:05:04 +03:00
|
|
|
connections](https://stackoverflow.com/questions/38169453/whats-the-relationship-between-profunctors-and-arrows)
|
|
|
|
among them. From now on, we'll be using them to provide a visual perspective of
|
|
|
|
profunctors:
|
|
|
|
|
|
|
|
![profunctor](diagram/profunctor.svg)
|
|
|
|
|
|
|
|
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`:
|
|
|
|
|
|
|
|
![profunctor-law1](diagram/profunctor-law1.svg)
|
|
|
|
|
|
|
|
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:
|
|
|
|
|
|
|
|
![profunctor-law2](diagram/profunctor-law2.svg)
|
|
|
|
|
|
|
|
It tells us that we can split a `dimap` which takes composed functions into a
|
|
|
|
composition of `dimap`s where each takes the corresponding uncomposed functions.
|
|
|
|
|
|
|
|
### Cartesian
|
|
|
|
|
|
|
|
Following down the profunctor family, we find `Cartesian`:
|
|
|
|
|
|
|
|
```haskell
|
|
|
|
class Profunctor p => Cartesian p where
|
|
|
|
first :: p a b -> p (a, c) (b, c)
|
|
|
|
second :: p a b -> p (c, a) (c, b)
|
|
|
|
```
|
|
|
|
|
2017-09-25 16:07:31 +03:00
|
|
|
These are the laws associated to this typeclass (skipping the counterparts for
|
|
|
|
`second`):
|
2017-09-21 15:05:04 +03:00
|
|
|
|
|
|
|
```haskell
|
|
|
|
dimap runit runit' h = first h
|
|
|
|
dimap assoc assoc' (first (first h)) = first h
|
|
|
|
-- where
|
2017-09-25 16:07:31 +03:00
|
|
|
runit :: (a, ()) -> a
|
|
|
|
runit' :: a -> (a, ())
|
2017-09-21 15:05:04 +03:00
|
|
|
assoc :: (a, (b, c)) -> ((a, b), c)
|
|
|
|
assoc' :: ((a, b), c) -> (a, (b, c))
|
|
|
|
```
|
|
|
|
|
|
|
|
The function instance for cartesian is straightforward:
|
|
|
|
|
|
|
|
```haskell
|
|
|
|
instance Cartesian (->) where
|
|
|
|
first f (a, c) = (f a, c)
|
|
|
|
second f (c, a) = ( c, f a)
|
|
|
|
```
|
|
|
|
|
2017-09-25 16:07:31 +03:00
|
|
|
#### Explanation
|
|
|
|
|
2017-09-21 15:05:04 +03:00
|
|
|
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:
|
|
|
|
|
|
|
|
![cartesian](diagram/cartesian.svg)
|
|
|
|
|
|
|
|
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:
|
|
|
|
|
|
|
|
![cartesian-law1](diagram/cartesian-law1.svg)
|
|
|
|
|
|
|
|
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:
|
|
|
|
|
|
|
|
![cartesian-law2](diagram/cartesian-law2.svg)
|
|
|
|
|
2017-09-25 16:07:31 +03:00
|
|
|
This representation seems more complex, but in essence, it states that nesting
|
|
|
|
`first`s doesn't break previous law. This is implicit in the diagram as well,
|
2022-08-13 10:28:50 +03:00
|
|
|
where `b` and `c` simply pass-through, regardless of the nested boxes in the
|
2017-09-25 16:07:31 +03:00
|
|
|
upper case.
|
2017-09-21 15:05:04 +03:00
|
|
|
|
|
|
|
### Cocartesian
|
|
|
|
|
|
|
|
Next, there is `Cocartesian`, whose primitives are shown in the following
|
|
|
|
typeclass:
|
|
|
|
|
|
|
|
```haskell
|
|
|
|
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)
|
|
|
|
```
|
|
|
|
|
2017-09-25 16:07:31 +03:00
|
|
|
Its laws are these ones (ignoring `right` counterparts):
|
2017-09-21 15:05:04 +03:00
|
|
|
|
|
|
|
```haskell
|
|
|
|
dimap rzero rzero' h = left h
|
|
|
|
dimap coassoc' coassoc (left (left h)) = left h
|
|
|
|
--where
|
2017-09-25 16:07:31 +03:00
|
|
|
rzero :: Either a Void -> a
|
|
|
|
rzero' :: a -> Either a Void
|
|
|
|
coassoc :: Either a (Either b c) -> Either (Either a b) c
|
2018-11-12 21:55:58 +03:00
|
|
|
coassoc' :: Either (Either a b) c -> Either a (Either b c)
|
2017-09-21 15:05:04 +03:00
|
|
|
```
|
|
|
|
|
|
|
|
And here it's the function instance:
|
|
|
|
|
|
|
|
```haskell
|
|
|
|
instance Cocartesian (->) where
|
|
|
|
left f = either (Left . f) Right
|
|
|
|
right f = either Left (Right . f)
|
|
|
|
```
|
|
|
|
|
2017-09-25 16:07:31 +03:00
|
|
|
#### Explanation
|
|
|
|
|
2017-09-21 15:05:04 +03:00
|
|
|
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
|
2017-09-21 16:24:11 +03:00
|
|
|
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:
|
2017-09-21 15:05:04 +03:00
|
|
|
|
|
|
|
![cocartesian](diagram/cocartesian.svg)
|
|
|
|
|
2017-09-25 16:07:31 +03:00
|
|
|
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
|
2017-09-21 15:05:04 +03:00
|
|
|
switch](http://lightwiring.co.uk/wp-content/uploads/2013/03/2-way-switching-2-wire-control-schematic-diagram.jpg)
|
|
|
|
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,
|
2017-09-25 16:07:31 +03:00
|
|
|
either activating the upper or the lower path. On the other hand, `right` is
|
2017-09-21 15:05:04 +03:00
|
|
|
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:
|
|
|
|
|
|
|
|
```haskell
|
|
|
|
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:
|
|
|
|
|
|
|
|
```haskell
|
|
|
|
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
|
2017-09-25 16:07:31 +03:00
|
|
|
lunit :: ((), a) -> a
|
|
|
|
lunit' :: a -> ((), a)
|
2017-09-21 15:05:04 +03:00
|
|
|
```
|
|
|
|
|
|
|
|
Instantiating this typeclass for function is trivial:
|
|
|
|
|
|
|
|
```haskell
|
|
|
|
instance Monoidal (->) where
|
|
|
|
par f g (a, c) = (f a, g c)
|
|
|
|
empty = id
|
|
|
|
```
|
|
|
|
|
2017-09-25 16:07:31 +03:00
|
|
|
#### Explanation
|
|
|
|
|
2017-09-21 16:24:11 +03:00
|
|
|
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:
|
2017-09-21 15:05:04 +03:00
|
|
|
|
|
|
|
![monoidal](diagram/monoidal.svg)
|
|
|
|
|
2017-09-21 16:24:11 +03:00
|
|
|
The resulting box make both arguments (`h` and `j`) coexist, by connecting them
|
|
|
|
in parallel (therefore the name `par`).
|
2017-09-21 15:05:04 +03:00
|
|
|
|
|
|
|
### 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](http://blog.sigfpe.com/2006/06/monads-kleisli-arrows-comonads-and.html):
|
|
|
|
|
|
|
|
```haskell
|
|
|
|
newtype UpStar f a b = UpStar { runUpStar :: a -> f b }
|
|
|
|
```
|
|
|
|
|
|
|
|
We can provide instances for many profunctor typeclasses:
|
|
|
|
|
|
|
|
```haskell
|
|
|
|
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))
|
|
|
|
|
2017-09-25 16:07:31 +03:00
|
|
|
-- XXX: `Pointed` should be good enough, but it lives in external lib
|
2017-09-21 15:05:04 +03:00
|
|
|
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:
|
|
|
|
|
|
|
|
```haskell
|
|
|
|
newtype DownStar f a b = DownStar { runDownStar :: f a -> b }
|
|
|
|
```
|
|
|
|
|
2019-01-14 13:37:12 +03:00
|
|
|
(You may not able to instantiate all three classes for `DownStar`. If so, try to
|
|
|
|
reason about why certain class cannot be instantiated.)
|
2019-01-13 03:33:20 +03:00
|
|
|
|
2017-09-25 16:07:31 +03:00
|
|
|
Take [`Tagged`](http://oleg.fi/gists/posts/2017-04-18-glassery.html) as another
|
|
|
|
example:
|
2017-09-21 15:05:04 +03:00
|
|
|
|
|
|
|
```haskell
|
|
|
|
newtype Tagged a b = Tagged { unTagged :: b }
|
|
|
|
```
|
|
|
|
|
2017-09-25 16:07:31 +03:00
|
|
|
This is just a wrapper for `b`s, 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:
|
2017-09-21 15:05:04 +03:00
|
|
|
|
|
|
|
```haskell
|
|
|
|
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.
|
|
|
|
|
2017-09-25 16:07:31 +03:00
|
|
|
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
|
2017-09-21 15:05:04 +03:00
|
|
|
there](https://ocharles.org.uk/blog/guest-posts/2013-12-22-24-days-of-hackage-profunctors.html).
|
2017-09-21 16:24:11 +03:00
|
|
|
As you see, profunctors also arise everywhere!
|
2017-09-22 14:35:47 +03:00
|
|
|
|
|
|
|
NEXT: [Profunctor Optics](ProfunctorOptics.md)
|