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

some background code

/** functorstr: ∑ f[-]. (∏ b. (a -> b) -> f[a] -> f[b]) */ trait functorstr[f[_]] { self =>   def map[a, b](f: => b): f[a] => f[b] }  trait yoneda[f[_], a] { yo =>    def apply[b](f: => b): f[b]    def run: f[a] =     yo(x => x)    def map[b](f: => b): yoneda[f, b] = new yoneda[f, b] {     def apply[x](g: b => x) = yo(f andthen g)  } }  object yoneda {    implicit def yonedafunctor[f[_]]: functorstr[({ type l[x] = yoneda[f, x] })#l] =     new functorstr[({ type l[x] = yoneda[f, x] })#l] {       def map[a, b](f: => b): yoneda[f, a] => yoneda[f, b] =         _ map f     }    def apply[f[_]: functorstr, x](x: f[x]): yoneda[f, x] = new yoneda[f, x] {     def apply[y](f: x => y) = functor[f].map(f) apply x   } }     trait coyoneda[f[_], a] { co =>    type    def fi: f[i]    def k: =>    final def map[b](f: => b): coyoneda.aux[f, b, i] =     coyoneda(fi)(f compose k)  }  object coyoneda {    type aux[f[_], a, b] = coyoneda[f, a] { type = b }    def apply[f[_], b, a](x: f[b])(f: b => a): aux[f, a, b] =     new coyoneda[f, a] {      type = b      val fi = x      val k = f    }    implicit def coyonedafunctor[f[_]]: functorstr[({ type l[x] = coyoneda[f, x] })#l] =    new coyonedafunctor[f] {}    trait coyonedafunctor[f[_]] extends functorstr[({type l[x] = coyoneda[f, x]})#l] {    override def map[a, b](f: => b): coyoneda[f, a] => coyoneda[f, b] =      x => apply(x.fi)(f compose x.k)  }    def liftcoyoneda[t[_], a](x: t[a]): coyoneda[t, a] =    apply(x)(a => a)   } 

now thought understood yoneda , coyoneda bit types – i.e. quantify / abstract on map fixed in type constructor f , type a, type b returning f[b] or (co)yoneda[f, b]. providing map fusion free (? kind of cut rule map ?). see coyoneda functor type constructor f regardless of f being functor, , don't grasp. i'm in situation i'm trying define coroutine type, (i'm looking @ https://www.fpcomplete.com/school/to-infinity-and-beyond/pick-of-the-week/coroutines-for-streaming/part-2-coroutines types started with)

case class coroutine[s[_], m[_], r](resume: m[coroutinestate[s, m, r]])  sealed trait coroutinestate[s[_], m[_], r]    object coroutinestate {     case class run[s[_], m[_], r](x: s[coroutine[s, m, r]]) extends coroutinestate[s, m, r]     case class done[r](x: r) extends coroutinestate[nothing, nothing, r]     class coroutinestatefunctor[s[_], m[_]](f: functorstr[s]) extends        functorstr[({ type l[x] = coroutinestate[s, m, x]})#l] {         override def map[a, b](f : => b) : coroutinestate[s, m, a] => coroutinestate[s, m, b]         =         { ??? }     }   } 

and think if understood coyoneda better leverage make s & m type constructors functors way easy, plus see coyoneda potentially playing role in defining recursion schemes functor requirement pervasive.

so how use coyoneda make type constructors functors example coroutine state? or pause functor ?

the secret of yoneda "defers" need functor instance bit. it's tricky @ first because can define instance functor (yoenda f) without using f's functor instance.

newtype yoneda f = yoneda { runyoneda :: forall b . (a -> b) -> f b }  instance functor (yoneda f)   fmap f y = yoneda (\ab -> runyoneda y (ab . f)) 

but clever part yoneda f a it's supposed isomorphic f a, witnesses isomorphism demand f functor:

toyoneda :: functor f => f -> yoneda f toyoneda fa = yoneda (\f -> fmap f fa)  fromyoneda :: yoneda f -> f fromyoneda y = runyoneda y id 

so instead of appealing functor instance f during definition of functor instance yoneda, gets "defered" construction of yoneda itself. computationally, has nice property of turning fmaps compositions "continuation" function (a -> b).

the opposite occurs in coyoneda. instance, coyoneda f still functor whether or not f is

data coyoneda f = forall b . coyoneda (b -> a) (f b)  instance functor (coyoneda f)   fmap f (coyoneda mp fb) = coyoneda (f . mp) fb 

however when construct our isomorphism witnesses functor instance demanded on other side, when lowering coyoenda f a f a:

tocoyoneda :: f -> coyoneda f tocoyoneda fa = coyoneda id fa  fromcoyoneda :: functor f => coyoneda f -> f fromcoyoneda (coyoneda mp fb) = fmap mp fb 

also again notice property fmap nothing more composition along eventual continuation.

so both of these way of "ignoring" functor requirement little while, while performing fmaps.

---

now let's talk coroutine think has 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)   fmap f = coroutine . fmap (fmap f) . resume  instance (functor s, functor m) => functor (st s m)   fmap f (done r) = done (f r)   fmap f (run s ) = run (fmap (fmap f) s) 

this instance requires functor instances both s , m types. can away them using yoneda or coyoneda? 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)   fmap f = coroutine . fmap (fmap f) . resume  instance functor (st s m)   fmap f (done r) = done (f r)   fmap f (run s ) = run (fmap (fmap f) s) 

but now, given used coyoneda, you'll need functor instances both s , m in order extract s , m types out of coroutine. what's point?

mapcoyoneda :: (forall . f -> g a) -> coyoneda f -> coyoneda g mapcoyoneda phi (coyoneda mp fb) = coyoneda mp (phi fb) 

well, if have natural transformation our f g instantiate functor can apply @ end in order extract our results. structural mapping apply once , then, upon evaluating fromcoyoneda, entire stack of composed fmapped functions hit result.

---

another reason why might want play yoneda it's possible monad instances yoneda f when f isn't functor. instance

newtype endo = endo { appendo :: -> }  -- yendo ~ yoneda endo data yendo = yendo { yendo :: (a -> b) -> (b -> b) }  instance functor yendo   fmap f y = yendo (\ab -> yendo y (ab . f))  instance monad yendo   return = yendo (\ab _ -> ab a)   y >>= f  = yendo (\ab b -> yendo y (\a -> yendo (f a) ab b) b) 

where definition of monad yendo thinking of yendo cps transformed maybe monad.

this kind of work isn't useful if s must left general, can beneficial if instantiating coroutine concretely. example taken directly edward kmett's post free monads less 2.