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

例如，可以使用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？还有其他用例吗？

最佳答案

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

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

Maybe下的Lam表示受抽象限制的变量；在Lam的主体中，变量Nothing指的是绑定(bind)变量，所有变量Just v表示环境中绑定(bind)的变量。 (>>=) :: Term v -> (v -> Term v') -> Term v'表示替换-可以将每个v ariable替换为Term。但是，在替换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融合为一个，因为在源代码中只有一个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。)

关于haskell - 从理论的角度来看，Yoneda Lemma仅有用吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56477752/