一步一步/深度解释:通过Coroutines的(Co)Yoneda(最好是scala)的力量

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只是从类型 - 即他们量化/抽象地图固定在某些类型构造函数F和某些类型a,到任何类型B返回F [B]或(Co)Yoneda [F ,B].因此,提供免费的地图融合(？这类似于地图的剪切规则？).但我发现Coyoneda是任何类型构造函数F的仿函数,不管F是一个Functor,而且我还没有完全掌握.现在我正处于尝试定义Coroutine类型的情况,(我正在考虑https://www.fpcomplete.com/school/to-infinity-and-beyond/pick-of-the-周/ 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

Yoneda的秘诀在于它"延迟"了对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自身的构造.在计算上,它还具有将所有fmaps转换为具有"延续"功能的组合的良好特性(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要求,特别是在执行fmaps时.

现在让我们谈谈这个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实例.我们可以通过使用或消除它们吗？基本上自动:smYonedaCoYoneda

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,整个堆栈的组合fmapped函数将达到结果.

你可能想要玩的另一个原因Yoneda是,即使甚至不是,也有可能获得Monad实例.例如Yoneda ffFunctor

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变换的Maybemonad 获得定义.

如果s必须保持一般性,这种工作显然没有用,但如果Coroutine具体实例化则可能是有益的.这个例子直接来自Edward Kmett的帖子Free Monads for Less 2.