Applicative 类型 class 实例的要求如何与它们对 Functor 的实现相关联
How do the requirements for the instances of the Applicative type class relate to their implementations for Functor
根据 Haskell 的库文档，Applicative class 的每个实例都必须满足四个规则：
- 身份：
pure id <*> v = v
- 成分：
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
- 同态：
pure f <*> pure x = pure (f x)
- 交汇处：
u <*> pure y = pure ($ y) <*> u
然后说作为这些规则的结果，底层 Functor 实例将满足 fmap f x = pure f <*> x。但是由于方法 fmap 甚至没有出现在上面的等式中，所以这个 属性 究竟是如何推导出来的？
更新：我已经大大扩展了答案。希望对你有帮助。
"Short"回答：
对于任何函子 F，类型都有一个 "free theorem"（见下文）：
(a -> b) -> F a -> F b
这个定理指出，对于任何（总）函数，比如 foo，对于这种类型，以下对于任何函数 f、f'、[=29 都成立=]，和 h，具有适当的匹配类型：
If f' . g = h . f, then foo f' . fmap g = fmap h . foo f.
请注意，为什么这是真的并不明显。
无论如何，如果你设置f = id和g = id并使用函子定律fmap id = id，这个定理可以简化为：
For all h, we have foo h = fmap h . foo id.
现在，如果 F 也是一个应用程序，那么函数：
foo :: (a -> b) -> F a -> F b
foo f x = pure f <*> x
类型正确，满足定理。因此，对于所有 h，我们有：
pure h <*> x
-- by definition of foo
= foo h x
-- by the specialized version of the theorem
= (fmap h . foo id) x
-- by definition of the operator (.)
= fmap h (foo id x)
-- by the definition of foo
= fmap h (pure id <*> x)
-- by the identity law for applicatives
= fmap h x
换句话说，应用程序的恒等律意味着关系：
pure h <*> x = fmap h x
不幸的是，文档没有包含对这个极其不明显事实的一些解释或至少承认。
更长的答案：
最初，文档列出了四个定律（身份、组合、同态和互换），以及 *> 和 <* 的两个附加定律，然后简单地说明：
The Functor instance should satisfy
fmap f x = pure f <*> x
上面的措辞已替换为新文本：
As a consequence of these laws, the Functor instance for f will satisfy
fmap f x = pure f <*> x
作为库列表中 Russell O'Connor 制作的 commit 92b562403 in February 2011 in response to a suggestion 的一部分。
Russell 指出，这条规则实际上是其他适用法律所隐含的。最初，他提供了以下证明（post 中的 link 已损坏，但我在 archive.org 上找到了副本）。他指出函数：
possibleFmap :: Applicative f => (a -> b) -> f a -> f b
possibleFmap f x = pure f <*> x
满足 fmap 的函子定律：
pure id <*> x = x {- Identity Law -}
pure (f . g) <*> x
= {- infix to prefix -}
pure ((.) f g) <*> x
= {- 2 applications of homomorphism law -}
pure (.) <*> pure f <*> pure g <*> x
= {- composition law -}
pure f <*> (pure g <*> x)
然后推断：
So, \f x -> pure f <*> x satisfies the laws of a functor.
Since there is at most one functor instance per data type,
(\f x -> pure f <*> x) = fmap.
这个证明的一个关键部分是每个数据类型只有一个可能的仿函数实例（即只有一种定义 fmap 的方法）。
当被问到这个问题时，他给出了以下关于 fmap 唯一性的证明。
Suppose we have a functor f and another function
foo :: (a -> b) -> f a -> f b
Then as a consequence of the free theorem for foo, for any f :: a -> b
and any g :: b -> c.
foo (g . f) = fmap g . foo f
In particular, if foo id = id, then
foo g = foo (g . id) = fmap g . foo id = fmap g . id = fmap g
显然，这主要取决于 "consequence of the free theorem for foo"。后来，罗素意识到可以直接使用自由定理，连同适用的恒等律来证明所需的定律。这就是我在上面 "short answer" 中总结的内容。
自由定理...
那么这个 "free theorem" 业务呢？
自由定理的概念来自瓦德勒的一篇论文，"Theorems for Free"。这是 Stack Overflow question，link 到论文和其他一些资源。理解理论"for real"很难，但你可以直观地思考一下。让我们选择一个特定的函子，比如 Maybe。假设我们有一个具有以下类型的函数；
foo :: (a -> b) -> Maybe a -> Maybe b
foo f x = ...
请注意，无论 foo 的实现多么复杂和令人费解，相同的实现需要适用于所有类型 a 和 b。它对a一无所知，所以它不能做任何具有类型a值的事情，除了应用函数f ，这只是给它一个 b 值。它对 b 也一无所知，所以它不能 做 任何具有 b 值的事情，除了可能 return Just someBvalue.至关重要的是，这意味着 foo 执行的计算结构——它对输入值 x 做了什么，是否以及何时决定应用 f 等——是完全取决于 x 是 Nothing 还是 Just ...。想一想——foo 可以检查 x 以查看它是 Nothing 还是 Just someA。但是，如果它是 Just someA，它就无法了解值 someA 的任何信息：它不能按原样使用它，因为它不理解类型 a，并且它不能用 f someA 做任何事情，因为它不理解类型 b。所以，如果 x 是 Just someA，函数 foo 只能作用于它的 Just-ness，而不作用于基础值 someA.
这有一个显着的后果。如果我们要使用函数 g 来从 foo f x 下更改输入值，方法是：
foo f' (fmap g x)
因为fmap g没有改变x的Nothing-ness或Just-ness，这个改变对[=26的结构没有影响=]的计算。它的行为方式相同，以相同的方式处理 Nothing 或 Just ... 值，在完全相同的情况下应用 f' ，并且与之前应用 f,等等
这意味着，只要我们进行安排，使得 f' 作用于 g 转换后的值给出与 h 转换后的值相同的答案f 作用于原始值——换句话说，如果我们有：
f' . g = h . f
然后我们可以欺骗 foo 以与处理原始输入完全相同的方式处理我们的 g 转换后的输入，只要我们考虑 [=] 之后的输入变化26=] 通过对输出应用 h 完成了 运行ning:
foo f' (fmap g x) = fmap h (foo f x)
我不知道这是否令人信服，但这就是我们得到自由定理的方式：
If f' . g = h . f then foo f' . fmap g = fmap h . foo f.
它基本上说因为我们可以以 foo 不会注意到的方式转换输入（因为它的多态类型），所以无论我们转换输入和 运行 foo 或 运行 foo 首先转换它的输出。
根据 Haskell 的库文档，Applicative class 的每个实例都必须满足四个规则：
- 身份：
pure id <*> v = v - 成分：
pure (.) <*> u <*> v <*> w = u <*> (v <*> w) - 同态：
pure f <*> pure x = pure (f x) - 交汇处：
u <*> pure y = pure ($ y) <*> u
然后说作为这些规则的结果，底层 Functor 实例将满足 fmap f x = pure f <*> x。但是由于方法 fmap 甚至没有出现在上面的等式中，所以这个 属性 究竟是如何推导出来的？
更新：我已经大大扩展了答案。希望对你有帮助。
"Short"回答：
对于任何函子 F，类型都有一个 "free theorem"（见下文）：
(a -> b) -> F a -> F b
这个定理指出，对于任何（总）函数，比如 foo，对于这种类型，以下对于任何函数 f、f'、[=29 都成立=]，和 h，具有适当的匹配类型：
If
f' . g = h . f, thenfoo f' . fmap g = fmap h . foo f.
请注意，为什么这是真的并不明显。
无论如何，如果你设置f = id和g = id并使用函子定律fmap id = id，这个定理可以简化为：
For all
h, we havefoo h = fmap h . foo id.
现在，如果 F 也是一个应用程序，那么函数：
foo :: (a -> b) -> F a -> F b
foo f x = pure f <*> x
类型正确，满足定理。因此，对于所有 h，我们有：
pure h <*> x
-- by definition of foo
= foo h x
-- by the specialized version of the theorem
= (fmap h . foo id) x
-- by definition of the operator (.)
= fmap h (foo id x)
-- by the definition of foo
= fmap h (pure id <*> x)
-- by the identity law for applicatives
= fmap h x
换句话说，应用程序的恒等律意味着关系：
pure h <*> x = fmap h x
不幸的是，文档没有包含对这个极其不明显事实的一些解释或至少承认。
更长的答案：
最初，文档列出了四个定律（身份、组合、同态和互换），以及 *> 和 <* 的两个附加定律，然后简单地说明：
The
Functorinstance should satisfyfmap f x = pure f <*> x
上面的措辞已替换为新文本：
As a consequence of these laws, the
Functorinstance forfwill satisfyfmap f x = pure f <*> x
作为库列表中 Russell O'Connor 制作的 commit 92b562403 in February 2011 in response to a suggestion 的一部分。
Russell 指出，这条规则实际上是其他适用法律所隐含的。最初，他提供了以下证明（post 中的 link 已损坏，但我在 archive.org 上找到了副本）。他指出函数：
possibleFmap :: Applicative f => (a -> b) -> f a -> f b
possibleFmap f x = pure f <*> x
满足 fmap 的函子定律：
pure id <*> x = x {- Identity Law -} pure (f . g) <*> x = {- infix to prefix -} pure ((.) f g) <*> x = {- 2 applications of homomorphism law -} pure (.) <*> pure f <*> pure g <*> x = {- composition law -} pure f <*> (pure g <*> x)
然后推断：
So,
\f x -> pure f <*> xsatisfies the laws of a functor. Since there is at most one functor instance per data type,(\f x -> pure f <*> x) = fmap.
这个证明的一个关键部分是每个数据类型只有一个可能的仿函数实例（即只有一种定义 fmap 的方法）。
当被问到这个问题时，他给出了以下关于 fmap 唯一性的证明。
Suppose we have a functor
fand another functionfoo :: (a -> b) -> f a -> f bThen as a consequence of the free theorem for
foo, for anyf :: a -> band anyg :: b -> c.foo (g . f) = fmap g . foo fIn particular, if
foo id = id, thenfoo g = foo (g . id) = fmap g . foo id = fmap g . id = fmap g
显然，这主要取决于 "consequence of the free theorem for foo"。后来，罗素意识到可以直接使用自由定理，连同适用的恒等律来证明所需的定律。这就是我在上面 "short answer" 中总结的内容。
自由定理...
那么这个 "free theorem" 业务呢？
自由定理的概念来自瓦德勒的一篇论文，"Theorems for Free"。这是 Stack Overflow question，link 到论文和其他一些资源。理解理论"for real"很难，但你可以直观地思考一下。让我们选择一个特定的函子，比如 Maybe。假设我们有一个具有以下类型的函数；
foo :: (a -> b) -> Maybe a -> Maybe b
foo f x = ...
请注意，无论 foo 的实现多么复杂和令人费解，相同的实现需要适用于所有类型 a 和 b。它对a一无所知，所以它不能做任何具有类型a值的事情，除了应用函数f ，这只是给它一个 b 值。它对 b 也一无所知，所以它不能 做 任何具有 b 值的事情，除了可能 return Just someBvalue.至关重要的是，这意味着 foo 执行的计算结构——它对输入值 x 做了什么，是否以及何时决定应用 f 等——是完全取决于 x 是 Nothing 还是 Just ...。想一想——foo 可以检查 x 以查看它是 Nothing 还是 Just someA。但是，如果它是 Just someA，它就无法了解值 someA 的任何信息：它不能按原样使用它，因为它不理解类型 a，并且它不能用 f someA 做任何事情，因为它不理解类型 b。所以，如果 x 是 Just someA，函数 foo 只能作用于它的 Just-ness，而不作用于基础值 someA.
这有一个显着的后果。如果我们要使用函数 g 来从 foo f x 下更改输入值，方法是：
foo f' (fmap g x)
因为fmap g没有改变x的Nothing-ness或Just-ness，这个改变对[=26的结构没有影响=]的计算。它的行为方式相同，以相同的方式处理 Nothing 或 Just ... 值，在完全相同的情况下应用 f' ，并且与之前应用 f,等等
这意味着，只要我们进行安排，使得 f' 作用于 g 转换后的值给出与 h 转换后的值相同的答案f 作用于原始值——换句话说，如果我们有：
f' . g = h . f
然后我们可以欺骗 foo 以与处理原始输入完全相同的方式处理我们的 g 转换后的输入，只要我们考虑 [=] 之后的输入变化26=] 通过对输出应用 h 完成了 运行ning:
foo f' (fmap g x) = fmap h (foo f x)
我不知道这是否令人信服，但这就是我们得到自由定理的方式：
If
f' . g = h . fthenfoo f' . fmap g = fmap h . foo f.
它基本上说因为我们可以以 foo 不会注意到的方式转换输入（因为它的多态类型），所以无论我们转换输入和 运行 foo 或 运行 foo 首先转换它的输出。