Domanda Passo dopo passo / Approfondimento: Il potere di (Co) Yoneda (preferibilmente in scala) attraverso le coroutine


qualche codice di background

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

 }

Ora pensavo di aver capito yoneda e coyoneda un po 'solo dai tipi -  cioè  che quantificano / astraggono sulla mappa fissata in qualche tipo di costruttore   F e alcuni tipo a, a qualsiasi tipo B restituendo F [B] o (Co) Yoneda [F, B]. Fornendo così la fusione delle mappe gratuitamente (? È una specie di regola di taglio per la mappa?). Ma vedo che Coyoneda è un funtore per qualsiasi tipo di costruttore F, indipendentemente dal fatto che F sia un Functor,  e che non riesco a cogliere pienamente. Ora sono in una situazione in cui sto cercando di definire un tipo di Coroutine,  (Sto guardando https://www.fpcomplete.com/school/to-infinity-and-beyond/pick-of-the-week/coroutines-for-streaming/part-2-coroutines per i tipi con cui iniziare)

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

e penso che se avessi capito meglio Coyoneda, avrei potuto sfruttarlo per rendere i functors dei costruttori di S & M più facili, inoltre vedo che Coyoneda potrebbe potenzialmente giocare un ruolo nella definizione degli schemi di ricorsione  come il requisito del functor è pervasivo.

Quindi, come potrei usare il coyoneda per creare funtori di tipo costruttori come ad esempio lo stato di coroutine? o qualcosa come un funtore Pause?


28
2018-06-02 17:54


origine


risposte:


Il segreto di Yoneda è che "allontana" il bisogno di Functor istanza un po '. All'inizio è difficile perché possiamo definire instance Functor (Yoenda f) senza usare f'S Functor esempio.

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

Ma la parte intelligente su Yoneda f a è che dovrebbe essere isomorfo a f atuttavia i testimoni di questo isomorfismo lo esigono f è 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

Quindi, invece di fare appello al Functor istanza per f durante la definizione del Functor istanza per Yoneda, viene "rimandato" alla costruzione del Yoneda si. Computazionalmente, ha anche la buona proprietà di trasformare tutto fmaps in composizioni con la funzione "continuazione" (a -> b).

Avviene il contrario CoYoneda. Per esempio, CoYoneda f è ancora un Functor indipendentemente dal fatto 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

tuttavia ora quando costruiamo il nostro isomorfismo assistiamo al Functor l'istanza è richiesta dall'altra parte, quando si abbassa CoYoenda f a 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

Anche noi notiamo di nuovo la proprietà che fmap non è altro che composizione lungo la prosecuzione finale.

Quindi entrambi sono un modo per "ignorare" a Functor requisito per un po 'di tempo, soprattutto durante l'esecuzione fmapS.


Ora parliamo di questo Coroutine quale penso abbia un tipo di Haskell come

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)

Questa istanza richiede Functor istanze per entrambi s e m tipi. Possiamo eliminarli usando Yoneda o CoYoneda? Fondamentalmente automaticamente:

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)

ma ora, dato che l'ho usato CoYoneda, avrai bisogno Functor istanze per entrambi s e m per estrarre s e m tipi fuori dal tuo Coroutine. Quindi qual è il punto?

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

Bene, se abbiamo una trasformazione naturale dalla nostra f a a g che crea un'istanza Functor quindi possiamo applicarlo alla fine per estrarre i nostri risultati. Questa mappatura strutturale si applicherà solo una volta e poi, al momento della valutazione fromCoYoneda, l'intera pila di composti fmaple funzioni ped colpiranno il risultato.


Un altro motivo per cui potresti voler giocare Yoneda è che a volte è possibile ottenere Monad istanze per Yoneda f anche quando f non è nemmeno un Functor. Per esempio

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)

dove otteniamo la definizione di Monad YEndo pensando a YEndo come un CPS trasformato Maybe monade.

Questo tipo di lavoro ovviamente non è utile se s deve essere lasciato generale, ma può essere utile se l'istanziazione Coroutine concretamente. Questo esempio è stato preso direttamente dal post di Edward Kmett Monade gratis per meno 2.


32
2018-06-03 02:12