有一个 `(a -> b) -> b` 等同于有一个 `a` 吗？
Is having a `(a -> b) -> b` equivalent to having an `a`?
在纯函数式语言中，您唯一可以对值执行的操作就是对其应用函数。
换句话说，如果您想对类型 a 的值做任何有趣的事情，您需要一个类型为 f :: a -> b 的函数（例如），然后应用它。如果有人将类型 (a -> b) -> b 交给您 (flip apply) a，那么它是否适合替代 a？
你会怎么称呼类型为 (a -> b) -> b 的东西？看到它似乎是 a 的替代品，我很想称它为代理，或者来自 http://www.thesaurus.com/browse/proxy.
的东西
这个问题是window进入一些更深层次的概念。
首先，请注意这个问题有歧义。我们指的是 forall b. (a -> b) -> b 类型，以便我们可以用我们喜欢的任何类型实例化 b，还是指 (a -> b) -> b 用于我们无法选择的某些特定 b。
我们可以在 Haskell 中形式化这种区别，因此：
newtype Cont b a = Cont ((a -> b) -> b)
newtype Cod a = Cod (forall b. (a -> b) -> b)
这里我们看到了一些词汇。第一种是 Cont monad, the second is CodensityIdentity，虽然我对后一种术语的熟悉程度不足以用英语说出你应该怎么称呼它。
Cont b a 不能等同于 a 除非 a -> b 可以包含至少与 a 一样多的信息（请参阅下面的 Dan Robertson 评论）。因此，举例来说，注意你永远无法从 ContVoida.
中得到任何东西
Cod a 等价于 a。看到这个就足以见证同构：
toCod :: a -> Cod a
fromCod :: Cod a -> a
我将把它们的实现留作练习。如果真的要搞起来，可以尝试证明这对真的是同构。 fromCod . toCod = id 很简单，但是 toCod . fromCod = id 需要 free theorem 才能 Cod。
luqui 的回答非常好，但出于以下几个原因，我将对 forall b. (a -> b) -> b === a 提供另一种解释：首先，因为我认为对 Codensity 的概括有点过分热情。其次，因为这是将一堆有趣的东西联系在一起的机会。继续！
z5h的魔盒
想象一下，有人抛了一个硬币，然后把它放进了一个魔法盒子里。您看不到盒子内部，但如果您选择类型 b 并将类型为 Bool -> b 的函数传递给盒子，盒子将吐出一个 b。如果不看里面，我们能从这个盒子中了解到什么？我们可以了解硬币的状态吗？我们可以了解盒子使用什么机制来产生 b 吗？事实证明，我们可以两者兼顾。
我们可以将框定义为 rank 2 类型 Box Bool 的函数，其中
type Box a = forall b. (a -> b) -> b
(这里的rank 2类型是指盒子厂商选择a，盒子用户选择b。)
我们将 a 放入框中，然后关闭框，创建... 闭包。
-- Put the a in the box.
box :: a -> Box a
box a f = f a
例如，box True。部分应用只是创建闭包的一种巧妙方式！
现在，硬币是正面还是反面？由于我这个盒子用户允许选择b，我可以选择Bool并传入一个函数Bool -> Bool。如果我选择 id :: Bool -> Bool 那么问题是：盒子会吐出它包含的值吗？答案是盒子要么吐出它包含的值，要么吐出废话（像undefined这样的底值）。换句话说，如果您得到答案，那么该答案 必须 是正确的。
-- Get the a out of the box.
unbox :: Box a -> a
unbox f = f id
因为我们不能在 Haskell 中生成任意值，盒子唯一能做的有意义的事情就是将给定的函数应用于它隐藏的值。这是参数多态性的结果，也称为 parametricity.
现在，为了证明 Box a 与 a 同构，我们需要证明关于装箱和拆箱的两件事。我们需要证明你投入什么就得到什么，你可以投入什么就得到什么。
unbox . box = id
box . unbox = id
我会做第一个，第二个留作 reader 的练习。
unbox . box
= {- definition of (.) -}
\b -> unbox (box b)
= {- definition of unbox and (f a) b = f a b -}
\b -> box b id
= {- definition of box -}
\b -> id b
= {- definition of id -}
\b -> b
= {- definition of id, backwards -}
id
（如果这些证明看起来相当微不足道，那是因为 Haskell 中的所有（总）多态函数都是自然变换，而我们在这里 证明的是 自然性。参数化再次为我们提供了低价、低价的定理！）
作为 reader 的旁白和另一个练习，为什么我不能用 (.) 实际定义 rebox？
rebox = box . unbox
为什么我必须像某种洞穴人一样内联 (.) 自己的定义？
rebox :: Box a -> Box a
rebox f = box (unbox f)
（提示：box、unbox、(.)的类型是什么？）
Identity and Codensity 和米田，我的天啊！
现在，我们如何概括 Box？ luqui 使用 Codensity: both bs are generalized by an arbitrary type constructor which we will call f. This is the Codensity transform of f a.
type CodenseBox f a = forall b. (a -> f b) -> f b
如果我们修复 f ~ Identity 然后我们返回 Box。然而，还有另一种选择：我们可以只命中 return 类型 f:
type YonedaBox f a = forall b. (a -> b) -> f b
（我在这里用这个名字放弃了游戏，但我们会回到那个。）我们也可以在这里修复 f ~ Identity 以恢复 Box，但我们让box 用户传入的是普通函数而不是 Kleisli 箭头。为了理解 我们要概括的内容 ，让我们再看看 box 的定义：
box a f = f a
嗯，这只是 flip ($)，不是吗？事实证明，我们的其他两个框是通过泛化 ($) 构建的：CodenseBox 是部分应用的翻转单子绑定，YonedaBox 是部分应用的 flip fmap。 （这也解释了为什么 Codensity f 是 Monad 而 Yoneda f 是 Functor 对于 any 选择 f：创建一个的唯一方法是分别关闭绑定或 fmap。）此外，这两个深奥的范畴论概念实际上是许多工作程序员都熟悉的概念的概括：CPS 变换！
换句话说，YonedaBox 是米田嵌入，box/unbox 法则 YonedaBox 是米田引理的证明！
TL;DR:
forall b. (a -> b) -> b === a 是米田引理的一个实例。
其他答案很好地描述了类型 forall b . (a -> b) -> b 和 a 之间的关系，但我想指出一个警告，因为它会导致一些有趣的开放性问题，我一直在努力。
从技术上讲，forall b . (a -> b) -> b 和 a 在像 Haskell 这样的语言中 不是 同构，其中 (1) 允许您编写表达式不会终止并且 (2) 是按值调用（严格）或包含 seq。我的观点是 不是 挑剔或表明参数化在 Haskell 中被削弱（众所周知），但可能有巧妙的方法来加强它，并且在某些情况下像这样的意义回收同构。
有些 forall b . (a -> b) -> b 类型的术语不能表示为 a。要了解原因，让我们先看看 Rein 作为练习留下的证明 box . unbox = id。事实证明，这个证明实际上比他的回答中的那个更有趣，因为它在很大程度上依赖于参数化。
box . unbox
= {- definition of (.) -}
\m -> box (unbox m)
= {- definition of box -}
\m f -> f (unbox m)
= {- definition of unbox -}
\m f -> f (m id)
= {- free theorem: f (m id) = m f -}
\m f -> m f
= {- eta: (\f -> m f) = m -}
\m -> m
= {- definition of id, backwards -}
id
参数化发挥作用的有趣步骤是应用自由定理f (m id) = m f。 属性 是 forall b . (a -> b) -> b 的结果，m 的类型。如果我们将 m 视为内部具有类型 a 的基础值的框，那么 m 对其参数唯一能做的就是将其应用于该基础值，并且 return 结果。在左侧，这意味着 f (m id) 从框中提取基础值，并将其传递给 f。在右侧，这意味着 m 将 f 直接应用于基础值。
不幸的是，当我们有像下面的 m 和 f 这样的术语时，这个推理就不太成立了。
m :: (Bool -> b) -> b
m k = seq (k true) (k false)
f :: Bool -> Int
f x = if x then ⊥ else 2`
回想一下我们想要展示 f (m id) = m f
f (m id)
= {- definition f -}
if (m id) then ⊥ else 2
= {- definition of m -}
if (seq (id true) (id false)) then ⊥ else 2
= {- definition of id -}
if (seq true (id false)) then ⊥ else 2
= {- definition of seq -}
if (id false) then ⊥ else 2
= {- definition of id -}
if false then ⊥ else 2
= {- definition of if -}
2
m f
= {- definition of m -}
seq (f true) (f false)
= {- definition of f -}
seq (if true then ⊥ else 2) (f false)
= {- definition of if -}
seq ⊥ (f false)
= {- definition of seq -}
⊥
显然 2 不等于 ⊥ 所以我们失去了自由定理以及 a 和 (a -> b) -> b 之间的同构。但是到底发生了什么？本质上，m 不仅仅是一个表现良好的框，因为它将其参数应用于两个不同的基础值（并使用 seq 来确保这两个应用程序都被实际评估），我们可以通过传递来观察在终止于这些潜在值之一而不是另一个的延续中。换句话说，m id = false 并不是 m 作为 Bool 的忠实表示，因为它 'forgets' m 使用 [= 调用其输入这一事实83=] true 和 false。
问题是三件事相互作用的结果：
- 存在非终止。
- 序列的存在
forall b . (a -> b) -> b 类型的项可能会多次应用其输入。
绕过第 1 点或第 2 点的希望不大。不过，Linear types 可能会给我们一个解决第三个问题的机会。类型 a ⊸ b 的 线性函数 是类型 a 到类型 b 的函数，它必须恰好使用其输入一次。如果我们要求 m 具有类型 forall b . (a -> b) ⊸ b，那么这就排除了我们对自由定理的反例并且应该让我们证明 a 和 forall b . (a -> b) ⊸ b [=79 之间的同构=]即使存在非终止和 seq.
这真的很酷！它表明线性能够通过驯服效应来 'rescue' 有趣的特性，这些效应会使真正的方程式推理变得困难。
不过，还有一个大问题。我们还没有技术来证明类型 forall b . (a -> b) ⊸ b 所需的自由定理。事实证明，当前的逻辑关系（我们通常用于进行此类证明的工具）并未设计为以所需的方式考虑线性。此问题对为执行 CPS 翻译的编译器建立正确性有影响。
在纯函数式语言中，您唯一可以对值执行的操作就是对其应用函数。
换句话说，如果您想对类型 a 的值做任何有趣的事情，您需要一个类型为 f :: a -> b 的函数（例如），然后应用它。如果有人将类型 (a -> b) -> b 交给您 (flip apply) a，那么它是否适合替代 a？
你会怎么称呼类型为 (a -> b) -> b 的东西？看到它似乎是 a 的替代品，我很想称它为代理，或者来自 http://www.thesaurus.com/browse/proxy.
这个问题是window进入一些更深层次的概念。
首先，请注意这个问题有歧义。我们指的是 forall b. (a -> b) -> b 类型，以便我们可以用我们喜欢的任何类型实例化 b，还是指 (a -> b) -> b 用于我们无法选择的某些特定 b。
我们可以在 Haskell 中形式化这种区别，因此：
newtype Cont b a = Cont ((a -> b) -> b)
newtype Cod a = Cod (forall b. (a -> b) -> b)
这里我们看到了一些词汇。第一种是 Cont monad, the second is CodensityIdentity，虽然我对后一种术语的熟悉程度不足以用英语说出你应该怎么称呼它。
Cont b a 不能等同于 a 除非 a -> b 可以包含至少与 a 一样多的信息（请参阅下面的 Dan Robertson 评论）。因此，举例来说，注意你永远无法从 ContVoida.
Cod a 等价于 a。看到这个就足以见证同构：
toCod :: a -> Cod a
fromCod :: Cod a -> a
我将把它们的实现留作练习。如果真的要搞起来，可以尝试证明这对真的是同构。 fromCod . toCod = id 很简单，但是 toCod . fromCod = id 需要 free theorem 才能 Cod。
luqui 的回答非常好，但出于以下几个原因，我将对 forall b. (a -> b) -> b === a 提供另一种解释：首先，因为我认为对 Codensity 的概括有点过分热情。其次，因为这是将一堆有趣的东西联系在一起的机会。继续！
z5h的魔盒
想象一下，有人抛了一个硬币，然后把它放进了一个魔法盒子里。您看不到盒子内部，但如果您选择类型 b 并将类型为 Bool -> b 的函数传递给盒子，盒子将吐出一个 b。如果不看里面，我们能从这个盒子中了解到什么？我们可以了解硬币的状态吗？我们可以了解盒子使用什么机制来产生 b 吗？事实证明，我们可以两者兼顾。
我们可以将框定义为 rank 2 类型 Box Bool 的函数，其中
type Box a = forall b. (a -> b) -> b
(这里的rank 2类型是指盒子厂商选择a，盒子用户选择b。)
我们将 a 放入框中，然后关闭框，创建... 闭包。
-- Put the a in the box.
box :: a -> Box a
box a f = f a
例如，box True。部分应用只是创建闭包的一种巧妙方式！
现在，硬币是正面还是反面？由于我这个盒子用户允许选择b，我可以选择Bool并传入一个函数Bool -> Bool。如果我选择 id :: Bool -> Bool 那么问题是：盒子会吐出它包含的值吗？答案是盒子要么吐出它包含的值，要么吐出废话（像undefined这样的底值）。换句话说，如果您得到答案，那么该答案 必须 是正确的。
-- Get the a out of the box.
unbox :: Box a -> a
unbox f = f id
因为我们不能在 Haskell 中生成任意值，盒子唯一能做的有意义的事情就是将给定的函数应用于它隐藏的值。这是参数多态性的结果，也称为 parametricity.
现在，为了证明 Box a 与 a 同构，我们需要证明关于装箱和拆箱的两件事。我们需要证明你投入什么就得到什么，你可以投入什么就得到什么。
unbox . box = id
box . unbox = id
我会做第一个，第二个留作 reader 的练习。
unbox . box
= {- definition of (.) -}
\b -> unbox (box b)
= {- definition of unbox and (f a) b = f a b -}
\b -> box b id
= {- definition of box -}
\b -> id b
= {- definition of id -}
\b -> b
= {- definition of id, backwards -}
id
（如果这些证明看起来相当微不足道，那是因为 Haskell 中的所有（总）多态函数都是自然变换，而我们在这里 证明的是 自然性。参数化再次为我们提供了低价、低价的定理！）
作为 reader 的旁白和另一个练习，为什么我不能用 (.) 实际定义 rebox？
rebox = box . unbox
为什么我必须像某种洞穴人一样内联 (.) 自己的定义？
rebox :: Box a -> Box a
rebox f = box (unbox f)
（提示：box、unbox、(.)的类型是什么？）
Identity and Codensity 和米田，我的天啊！
现在，我们如何概括 Box？ luqui 使用 Codensity: both bs are generalized by an arbitrary type constructor which we will call f. This is the Codensity transform of f a.
type CodenseBox f a = forall b. (a -> f b) -> f b
如果我们修复 f ~ Identity 然后我们返回 Box。然而，还有另一种选择：我们可以只命中 return 类型 f:
type YonedaBox f a = forall b. (a -> b) -> f b
（我在这里用这个名字放弃了游戏，但我们会回到那个。）我们也可以在这里修复 f ~ Identity 以恢复 Box，但我们让box 用户传入的是普通函数而不是 Kleisli 箭头。为了理解 我们要概括的内容 ，让我们再看看 box 的定义：
box a f = f a
嗯，这只是 flip ($)，不是吗？事实证明，我们的其他两个框是通过泛化 ($) 构建的：CodenseBox 是部分应用的翻转单子绑定，YonedaBox 是部分应用的 flip fmap。 （这也解释了为什么 Codensity f 是 Monad 而 Yoneda f 是 Functor 对于 any 选择 f：创建一个的唯一方法是分别关闭绑定或 fmap。）此外，这两个深奥的范畴论概念实际上是许多工作程序员都熟悉的概念的概括：CPS 变换！
换句话说，YonedaBox 是米田嵌入，box/unbox 法则 YonedaBox 是米田引理的证明！
TL;DR:
forall b. (a -> b) -> b === a 是米田引理的一个实例。
其他答案很好地描述了类型 forall b . (a -> b) -> b 和 a 之间的关系，但我想指出一个警告，因为它会导致一些有趣的开放性问题，我一直在努力。
从技术上讲，forall b . (a -> b) -> b 和 a 在像 Haskell 这样的语言中 不是 同构，其中 (1) 允许您编写表达式不会终止并且 (2) 是按值调用（严格）或包含 seq。我的观点是 不是 挑剔或表明参数化在 Haskell 中被削弱（众所周知），但可能有巧妙的方法来加强它，并且在某些情况下像这样的意义回收同构。
有些 forall b . (a -> b) -> b 类型的术语不能表示为 a。要了解原因，让我们先看看 Rein 作为练习留下的证明 box . unbox = id。事实证明，这个证明实际上比他的回答中的那个更有趣，因为它在很大程度上依赖于参数化。
box . unbox
= {- definition of (.) -}
\m -> box (unbox m)
= {- definition of box -}
\m f -> f (unbox m)
= {- definition of unbox -}
\m f -> f (m id)
= {- free theorem: f (m id) = m f -}
\m f -> m f
= {- eta: (\f -> m f) = m -}
\m -> m
= {- definition of id, backwards -}
id
参数化发挥作用的有趣步骤是应用自由定理f (m id) = m f。 属性 是 forall b . (a -> b) -> b 的结果，m 的类型。如果我们将 m 视为内部具有类型 a 的基础值的框，那么 m 对其参数唯一能做的就是将其应用于该基础值，并且 return 结果。在左侧，这意味着 f (m id) 从框中提取基础值，并将其传递给 f。在右侧，这意味着 m 将 f 直接应用于基础值。
不幸的是，当我们有像下面的 m 和 f 这样的术语时，这个推理就不太成立了。
m :: (Bool -> b) -> b
m k = seq (k true) (k false)
f :: Bool -> Int
f x = if x then ⊥ else 2`
回想一下我们想要展示 f (m id) = m f
f (m id)
= {- definition f -}
if (m id) then ⊥ else 2
= {- definition of m -}
if (seq (id true) (id false)) then ⊥ else 2
= {- definition of id -}
if (seq true (id false)) then ⊥ else 2
= {- definition of seq -}
if (id false) then ⊥ else 2
= {- definition of id -}
if false then ⊥ else 2
= {- definition of if -}
2
m f
= {- definition of m -}
seq (f true) (f false)
= {- definition of f -}
seq (if true then ⊥ else 2) (f false)
= {- definition of if -}
seq ⊥ (f false)
= {- definition of seq -}
⊥
显然 2 不等于 ⊥ 所以我们失去了自由定理以及 a 和 (a -> b) -> b 之间的同构。但是到底发生了什么？本质上，m 不仅仅是一个表现良好的框，因为它将其参数应用于两个不同的基础值（并使用 seq 来确保这两个应用程序都被实际评估），我们可以通过传递来观察在终止于这些潜在值之一而不是另一个的延续中。换句话说，m id = false 并不是 m 作为 Bool 的忠实表示，因为它 'forgets' m 使用 [= 调用其输入这一事实83=] true 和 false。
问题是三件事相互作用的结果：
- 存在非终止。
- 序列的存在
forall b . (a -> b) -> b类型的项可能会多次应用其输入。
绕过第 1 点或第 2 点的希望不大。不过，Linear types 可能会给我们一个解决第三个问题的机会。类型 a ⊸ b 的 线性函数 是类型 a 到类型 b 的函数，它必须恰好使用其输入一次。如果我们要求 m 具有类型 forall b . (a -> b) ⊸ b，那么这就排除了我们对自由定理的反例并且应该让我们证明 a 和 forall b . (a -> b) ⊸ b [=79 之间的同构=]即使存在非终止和 seq.
这真的很酷！它表明线性能够通过驯服效应来 'rescue' 有趣的特性，这些效应会使真正的方程式推理变得困难。
不过，还有一个大问题。我们还没有技术来证明类型 forall b . (a -> b) ⊸ b 所需的自由定理。事实证明，当前的逻辑关系（我们通常用于进行此类证明的工具）并未设计为以所需的方式考虑线性。此问题对为执行 CPS 翻译的编译器建立正确性有影响。