scala - 一步一步/深入解释 : The Power of (Co)Yoneda (preferably in scala) through Coroutines

Question

一些后台代码

/** FunctorStr: ∑ F[-]. (∏ A B. (A -> B) -> F[A] -> F[B]) */
trait FunctorStr[F[_]] { self =>
  def map[A, B](f: A => B): F[A] => F[B]
}

trait Yoneda[F[_], A] { yo =>

  def apply[B](f: A => B): F[B]

  def run: F[A] =
    yo(x => x)

  def map[B](f: A => 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: A => 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 I

  def fi: F[I]

  def k: I => A

  final def map[B](f: A => B): Coyoneda.Aux[F, B, I] =
    Coyoneda(fi)(f compose k)

}

object Coyoneda {

  type Aux[F[_], A, B] = Coyoneda[F, A] { type I = B }

  def apply[F[_], B, A](x: F[B])(f: B => A): Aux[F, A, B] =
    new Coyoneda[F, A] {
     type I = 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: A => 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)

 }

现在我想我只是从类型上理解了 yoneda 和 coyoneda – IE。 他们对固定在某种类型构造函数中的映射进行量化/抽象 F 和某些类型 a，对于返回 F[B] 或 (Co)Yoneda[F, B] 的任何类型 B。从而免费提供 map 融合(？这有点像 map 的切割规则吗？)。但我发现 Coyoneda 是任何类型构造函数 F 的仿函数，无论 F 是仿函数， 我还没有完全理解。现在我正处于尝试定义 Coroutine 类型的情况， (我正在查看 https://www.fpcomplete.com/school/to-infinity-and-beyond/pick-of-the-week/coroutines-for-streaming/part-2-coroutines 以了解要开始使用的类型)

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 : A => B) : CoroutineState[S, M, A] => CoroutineState[S, M, B]
        =
        { ??? }
    }
  }

我认为，如果我更好地理解 Coyoneda，我可以利用它来使 S & M 类型构造函数变得简单，而且我认为 Coyoneda 可能在定义递归方案中发挥作用 因为仿函数要求是普遍存在的。

那么我如何使用 coyoneda 来创建类型构造函数仿函数，例如协程状态？或者类似 Pause 仿函数的东西？

Answer 1

米田的 secret 在于它“推迟”了 Functor 的需要举个例子吧。一开始这很棘手，因为我们可以定义 instance Functor (Yoenda f)不使用f的Functor实例。

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))

但是关于Yoneda f a的聪明部分它应该与 f a 同构，然而，这种同构的见证者要求 f是 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

所以不要诉诸 Functor f 的实例在定义Functor期间Yoneda 的实例，它被“推迟”到 Yoneda 的构造本身。在计算上，它还具有将所有fmap翻转的良好属性。 s 进入具有“继续”功能的组合 (a -> b) .

相反的情况出现在 CoYoneda 中。例如，CoYoneda f仍然是Functor是否f是

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

但是现在，当我们构造我们的同构时，见证了 Functor当降低 CoYoenda f a 时，另一侧需要实例至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

我们再次注意到 fmap 的属性无非是沿着最终的延续进行组合。

所以这两种方式都是“忽略” Functor 的一种方式。需要一段时间，特别是在执行fmap时s。

<小时/>

现在我们来谈谈这个Coroutine我认为它具有像 Haskell 类型

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)

此实例需要 Functor s 的实例和m类型。我们可以通过使用 Yoneda 来消除它们吗？或CoYoneda ？基本上自动:

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)

但是现在，鉴于我使用了 CoYoneda ，您需要Functor两者的实例 s和m为了提取s和m从您的 Coroutine 中输入。那么有什么意义呢？

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

好吧，如果我们从 f 有一个自然的转变到 g它实例化 Functor然后我们可以在最后应用它来提取我们的结果。此结构映射将仅应用一次，然后在评估 fromCoYoneda 时应用。 ，整个堆栈由 fmap 组成ped 函数将得出结果。

<小时/>

您可能想玩 Yoneda 的另一个原因是有时可以获得 Monad Yoneda f 的实例即使f甚至不是Functor 。例如

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)

我们在这里得到 Monad YEndo 的定义通过思考YEndo作为 CPS 改造 Maybe单子(monad)。

这种工作显然没有用，如果 s必须保持通用，但如果实例化则可能会有所帮助 Coroutine具体来说。此示例直接取自 Edward Kmett 的帖子 Free Monads for Less 2 .