Пошаговое / глубокое объяснение: Сила (Со) Йонеды (предпочтительно в Скале) через сопрограммы

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, Б]. Таким образом, предоставляется объединение карт бесплатно ("это что-то вроде правила обрезки для карты"). Но я вижу, что Койонеда является функтором для любого конструктора типов F, независимо от того, является ли F функтором, и что я не совсем понимаю. Сейчас я нахожусь в ситуации, когда я пытаюсь определить тип сопрограммы (я смотрю на 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

Секрет Йонеды в том, что она "откладывает" необходимость Functor экземпляр немного. Сначала это сложно, потому что мы можем определить instance Functor (Yoenda f) без использования f "s 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)

Этот экземпляр требует 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 Функции педали попадут в результат.

---

Еще одна причина, почему вы можете играть с 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 монада.

Такая работа, очевидно, бесполезна, если s должен быть оставлен общим, но может быть полезным в случае Coroutine конкретно. Этот пример был взят непосредственно из поста Эдварда Кметта " Свободные монады для меньших 2".