米田引理仅在理论上有用吗？

Question

比如loop fusion可以用米田获得：

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

嗯，在这种情况下你可以手工完成融合，因为源代码中的两个 fmap 是 "visible"，但是重点是 Yoneda 在运行时进行转换。这是一个动态的东西，当您不知道您需要fmap遍历一个结构多少次时最有用。例如。考虑 lambda 项：

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

Lam下的Maybe表示抽象绑定的变量；在Lam的主体中，变量Nothing指的是绑定变量，所有变量Just v代表环境中绑定的变量。 (>>=) :: Term v -> (v -> Term v') -> Term v' 表示替换——每个 v 变量都可以用 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 都会在 f 中添加一个 fmap Just。如果我有一个 Var v 埋在 1000 Lams 之下，那么我最终会调用 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, 之前。)

Answer 2

有一个在本质上与 in lens. A look at (a paraphrased version of) the lens function 相似的示例说明了典型的 van 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 中的实现使用大量内联和新类型强制转换，因此在使用 lens 组合器（view、over 等），所涉及的函子（通常是 Const 或 Identity）通常会被优化掉。然而，在某些情况下，这是不可能做到的（例如，如果镜头的使用方式导致在编译时无法具体选择函子）。作为补偿，lens 提供了一个名为 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 融合。

（这个答案的灵感来自 a comment by Edward Kmett，我在看到这个问题之前偶然发现了它。）

米田引理仅在理论上有用吗？

Is the Yoneda Lemma only useful from a theoretical point of view?

haskell

functor

function-composition