Paso a paso/explicación profunda: El poder de(Co) Yoneda(preferiblemente en scala) a través de Coroutines

haskell category-theory

Question

algún código de fondo

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

 }

Ahora pensé que entendía yoneda y coyoneda un poco solo de los tipos, es decir, que cuantifican / resumen sobre el mapa fijo en algún tipo constructor F y algún tipo a, a cualquier tipo B que devuelve F [B] o (Co) Yoneda [F , B]. Por lo tanto, proporcionar una fusión de mapas gratis (¿es esto una especie de regla de corte para un mapa?). Pero veo que Coyoneda es un functor para cualquier constructor de tipo F, independientemente de que F sea un Functor, y eso no lo entiendo completamente. Ahora estoy en una situación en la que estoy tratando de definir un tipo de Coroutine, (estoy viendo https://www.fpcomplete.com/school/to-infinity-and-beyond/pick-of-the-week/coroutines-for-streaming/part-2-coroutines para que los tipos comiencen con

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]
        =
        { ??? }
    }
  }

y creo que si entendiera mejor a Coyoneda, podría aprovecharlo para hacer que los constructores de tipo S&M funcionen de manera muy sencilla, además veo que Coyoneda puede jugar un papel importante en la definición de esquemas de recursión, ya que el requisito del funtor es generalizado.

Entonces, ¿cómo podría usar coyoneda para hacer que los constructores de tipos funcionen como, por ejemplo, el estado coroutine? ¿O algo así como un funtor de pausa?

Answer 1

El secreto de Yoneda es que "difiere" un poco la necesidad de la instancia de Functor . Es complicado al principio porque podemos definir la instance Functor (Yoenda f) sin usar la instancia de 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))

Pero la parte inteligente de Yoneda fa es que se supone que es isomorfo a fa , sin embargo, los testigos de este isomorfismo exigen que f sea ​​un 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

Entonces, en lugar de apelar a la instancia de Functor para f durante la definición de la instancia de Functor para Yoneda , se "difiere" a la construcción del propio Yoneda . Desde el punto de vista informático, también tiene la agradable propiedad de convertir todos los fmap s en composiciones con la función de "continuación" (a -> b) .

Ocurre lo contrario en CoYoneda . Por ejemplo, CoYoneda f sigue siendo un Functor sea ​​o no 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

Sin embargo, ahora, cuando construimos nuestros testigos de isomorfismo, la instancia de Functor se exige en el otro lado, al bajar CoYoenda fa a fa :

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

También notamos de nuevo la propiedad de que fmap no es más que una composición a lo largo de la eventual continuación.

Por lo tanto, ambos son una forma de "ignorar" un requisito de Functor por un momento, especialmente al realizar fmap s.

Ahora hablemos de este Coroutine que creo que tiene un tipo de Haskell como

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)

Esta instancia requiere instancias de Functor para los tipos s m . ¿Podemos eliminarlos usando Yoneda o CoYoneda ? Básicamente de forma automática:

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)

pero ahora, dado que usé CoYoneda , necesitarás instancias de Functor para CoYoneda para extraer s tipos Coroutine de tu Coroutine . ¿Entonces cuál es el punto?

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

Bueno, si tenemos una transformación natural de nuestra f a una g lo que Functor instancia de Functor , podemos aplicarla al final para extraer nuestros resultados. Este mapeo estructural solo se aplicará una vez y luego, al evaluar desde fromCoYoneda , toda la pila de funciones compuestas de fmap de fmap alcanzará el resultado.

Otra razón por la que podrías querer jugar con Yoneda es que a veces es posible obtener instancias de Yoneda f para Yoneda f incluso cuando f no es ni siquiera un Functor . Por ejemplo

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)

donde obtenemos la definición de Monad YEndo al pensar en YEndo como una CPS transformada. Maybe monada.

Este tipo de trabajo, obviamente, no es útil si s debe dejarse en general, pero puede ser beneficioso si se ejemplifica concretamente Coroutine . Este ejemplo fue tomado directamente de la publicación Free Monads for Less 2 de Edward Kmett.