从理论的角度来看，Yoneda Lemma仅有用吗？

Question

例如，可以使用Yoneda获得循环融合：

newtype Yoneda f a =
    Yoneda (forall b. (a -> b) -> f b)

liftYo :: (Functor f) => f a -> Yoneda f a
liftYo x = Yoneda $ \f -> fmap f x

lowerYo :: (Functor f) => Yoneda f a -> f a
lowerYo (Yoneda y) = y id

instance Functor (Yoneda f) where
    fmap f (Yoneda y) = Yoneda $ \g -> y (g . f)

loopFusion = lowerYo . fmap f . fmap g . liftYo

但是我本来可以写的loopFusion = fmap (f . g)。我为什么要使用Yoneda？还有其他用例吗？

Answer 1

好吧，在这种情况下，您可以手工完成融合，因为这两个fmaps在源代码中是“可见的”，但是重点是Yoneda在运行时进行了转换。这是动态的，当您不知道需要fmap遍历一个结构多少次时最有用。例如考虑lambda条款：

data Term v = Var v | App (Term v) (Term v) | Lam (Term (Maybe v))

所述Maybe下Lam表示由抽象约束变量; 在a的主体中Lam，变量Nothing指的是绑定变量，所有变量Just v代表环境中绑定的变量。(>>=) :: Term v -> (v -> Term v') -> Term v'表示替换-每个variable均可替换为Term。但是，当替换a内Lam的变量时，产生的所有变量都Term需要包装在中Just。例如

Lam $ Lam $ Var $ Just $ Just $ ()
  >>= \() -> App (Var "f") (Var "x")
=
Lam $ Lam $ App (Var $ Just $ Just "f") (Var $ Just $ Just "x")

天真的实现是(>>=)这样的：

(>>=) :: Term v -> (v -> Term v') -> Term v'
Var x >>= f = f x
App l r >>= f = App (l >>= f) (r >>= f)
Lam b >>= f = Lam (b >>= maybe (Var Nothing) (fmap Just . f))

但是，这样写，每次Lam说(>>=)去下增加了一个fmap Just到f。如果我的Var v埋葬时间少于1000 Lam秒，那么我将fmap Just在新的f v学期中调用并迭代1000次！我不能随便fmap用手把多个s融合在一起，因为fmap在源代码中只有一个被多次调用。

Yoneda 可以缓解疼痛：

bindTerm :: Term v -> (v -> Yoneda Term v') -> Term v'
bindTerm (Var x) f = lowerYoneda (f x)
bindTerm (App l r) f = App (bindTerm l f) (bindTerm r f)
bindTerm (Lam b) f =
  Lam (bindTerm b (maybe (liftYoneda $ Var Nothing) (fmap Just . f)))

(>>=) :: Term v -> (v -> Term v') -> Term v'
t >>= f = bindTerm t (liftYoneda . f)

现在，fmap Just免费。这只是一个奇怪的功能组成。产生的实际迭代Term在中lowerYoneda，每个仅调用一次Var。重申一下：源代码无处包含任何形式的fmap f (fmap g x)。此类形式仅在运行时动态产生，具体取决于的参数(>>=)。Yoneda可以重写，在运行时，要fmap (f . g) x，即使你无法将它改写一样，在源代码。此外，您可以Yoneda对现有代码进行最少的更改。（有，然而，一个缺点：lowerYoneda是始终调用一次为每个Var装置，该装置例如Var v >>= f = fmap id (f v)它只是f v，之前。）

Answer 2

在精神上有一个例子与HTNW在镜头中描述的例子相似。一看（中转述的版本）的lens功能说明是一个典型的面包车Laarhoven镜头的样子：

-- type Lens s t a b = forall f. Functor f => (a -> f b) -> s -> f t
lens :: (s -> a) -> (s -> b -> t) -> Lens s t a b
lens getter setter = \f -> \s -> fmap (setter s) (f (getter s))

出现fmap意味着从原理上讲，组成镜头将导致的连续使用fmap。现在，大多数情况下，这实际上并不重要：lens中的实现使用大量的内联和新类型强制，因此，在使用透镜组合器（view，over等）时，通常涉及的函子（通常为Const或Identity）优化了。但是，在某些情况下，是不可能做到这一点的（例如，如果使用镜头的方式是在编译时未对函子进行具体选择）。作为补偿，镜片提供了称为的辅助功能fusing，使您可以fmap在那些特殊情况下的融合。它的实现是：

-- type LensLike f s t a b = (a -> f b) -> s -> f t
fusing :: Functor f => LensLike (Yoneda f) s t a b -> LensLike f s t a b
fusing t = \f -> lowerYoneda . t (liftYoneda . f)

这样，如果您编写了fusing (foo . bar)，就Yoneda f被选作的函子foo . bar，从而保证了fmap融合。

（此答案是由爱德华·克梅特（Edward Kmett）的评论启发而来的，在碰到这个问题之前，我偶然发现了这一评论。）