Шаг за шагом/Глубокое объяснение: Сила (Co) Yoneda (предпочтительно в scala) через Coroutines

некоторый код фона

/** 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-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 для создания функторов конструкторов типов, таких как, например, coroutine state? или что-то вроде функции Pause?

Ответ 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. Вычислительно, он также обладает хорошим свойством превратить все fmap в композиции с функцией "продолжения" (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)

Для этого экземпляра для экземпляров s и m требуются экземпляры Functor. Можем ли мы покончить с ними, используя 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 конкретным образом. Этот пример был взят непосредственно из сообщения Эдварда Кеммета Free Monads для менее 2.