Step by Step / Deep explain: The Power of (Co)Yoneda (preferably in scala) through Coroutines

category-theory, haskell, scala

Solution

The secret of Yoneda is that it "defers" the need for the `Functor` instance a bit. It's tricky at first because we can define `instance Functor (Yoenda f)` without using `f`'s `Functor` instance.

newtype Yoneda f a = Yoneda { runYoneda :: forall b . (a -> b) -> f b }

instance Functor (Yoneda f) where
  fmap f y = Yoneda (\ab -> runYoneda y (ab . f))

But the clever part about `Yoneda f a` is that it's supposed to be isomorphic to `f a`, however the witnesses to this isomorphism demand that `f` is a `Functor`:

toYoneda :: Functor f => f a -> Yoneda f a
toYoneda fa = Yoneda (\f -> fmap f fa)

fromYoneda :: Yoneda f a -> f a
fromYoneda y = runYoneda y id

So instead of appealing to the `Functor` instance for `f` during definition of the `Functor` instance for `Yoneda`, it gets "defered" to the construction of the `Yoneda` itself. Computationally, it also has the nice property of turning all `fmap`s into compositions with the "continuation" function `(a -> b)`.

The opposite occurs in `CoYoneda`. For instance, `CoYoneda f` is still a `Functor` whether or not `f` is

data CoYoneda f a = forall b . CoYoneda (b -> a) (f b)

instance Functor (CoYoneda f) where
  fmap f (CoYoneda mp fb) = CoYoneda (f . mp) fb

however now when we construct our isomorphism witnesses the `Functor` instance is demanded on the other side, when lowering `CoYoenda f a` to `f a`:

toCoYoneda :: f a -> CoYoneda f a
toCoYoneda fa = CoYoneda id fa

fromCoYoneda :: Functor f => CoYoneda f a -> f a
fromCoYoneda (CoYoneda mp fb) = fmap mp fb

Also we again notice the property that `fmap` is nothing more than composition along the eventual continuation.

So both of these are a way of "ignoring" a `Functor` requirement for a little while, especially while performing `fmap`s.

Now let's talk about this `Coroutine` which I think has a Haskell type like

data Coroutine s m r = Coroutine { resume :: m (St s m r) }
data St s m r = Run (s (Coroutine s m r)) | Done r

instance (Functor s, Functor m) => Functor (Coroutine s m) where
  fmap f = Coroutine . fmap (fmap f) . resume

instance (Functor s, Functor m) => Functor (St s m) where
  fmap f (Done r) = Done (f r)
  fmap f (Run s ) = Run (fmap (fmap f) s)

This instance this requires `Functor` instances for both the `s` and `m` types. Can we do away with them by using `Yoneda` or `CoYoneda`? Basically automatically:

data Coroutine s m r = Coroutine { resume :: CoYoneda m (St s m r) }
data St s m r = Run (CoYoneda s (Coroutine s m r)) | Done r

instance Functor (Coroutine s m) where
  fmap f = Coroutine . fmap (fmap f) . resume

instance Functor (St s m) where
  fmap f (Done r) = Done (f r)
  fmap f (Run s ) = Run (fmap (fmap f) s)

but now, given that I used `CoYoneda`, you'll need `Functor` instances for both `s` and `m` in order to extract `s` and `m` types out of your `Coroutine`. So what's the point?

mapCoYoneda :: (forall a . f a -> g a) -> CoYoneda f a -> CoYoneda g a
mapCoYoneda phi (CoYoneda mp fb) = CoYoneda mp (phi fb)

Well, if we have a natural transformation from our `f` to a `g` which does instantiate `Functor` then we can apply that at the end in order to extract our results. This structural mapping will only apply once and then, upon evaluating `fromCoYoneda`, the entire stack of composed `fmap`ped functions will hit the result.

Another reason why you might want to play with `Yoneda` is that it's sometimes possible to get `Monad` instances for `Yoneda f` even when `f` isn't even a `Functor`. For instance

newtype Endo a = Endo { appEndo :: a -> a }

-- YEndo ~ Yoneda Endo
data YEndo a = YEndo { yEndo :: (a -> b) -> (b -> b) }

instance Functor YEndo where
  fmap f y = YEndo (\ab -> yEndo y (ab . f))

instance Monad YEndo where
  return a = YEndo (\ab _ -> ab a)
  y >>= f  = YEndo (\ab b -> yEndo y (\a -> yEndo (f a) ab b) b)

where we get the definition of `Monad YEndo` by thinking of `YEndo` as a CPS transformed `Maybe` monad.

This kind of work obviously isn't useful if `s` must be left general, but can be beneficial if instantiating `Coroutine` concretely. This example was taken directly from Edward Kmett's post Free Monads for Less 2.

Problem

Original source