如何理解类型 a 和 forall r。 (a -> r) -> r 是同构的
How to understand that the types a and forall r. (a -> r) -> r are isomorphic
在书Thinking with Types中，6.4 Continuation Monad说类型a和forall r. (a -> r) -> r是同构的，可以通过以下函数证明：
cont :: a -> (forall r. (a -> r) -> r)
cont x = \f -> f x
unCont :: (forall r. (a -> r) -> r) -> a
unCont f = f id
在这本书中，它告诉我们具有相同基数的任何两个类型总是彼此同构的。所以我试图找出类型的基数a 和 forall r. (a -> r) -> r.
假设 a 类型的基数是 |a|。那么对于类型forall r. (a -> r) -> r，如何计算出它的基数等于|a|呢？函数类型 a -> b 的基数为 |b|^|a|，即 |b| 的 |a| 次方，因此 forall r. (a -> r) -> r 的基数为 |r|^(|r|^|a|)。怎么可能等于|a|？
我很困惑。感谢您的任何提示！
基数参数实际上不适用于多态类型（请参阅@chi 的回答）。
但是同构本身可以这样直观地解释：
类型 forall r. (a -> r) -> r 表示“如果你给我一个将 a 转换为 r 的函数，我可以还给你一个 r . 哦，我可以为任何可能的 r 做到这一点 "
要实现这样的承诺，唯一的办法就是偷偷地把a拿在手上。
由于我承诺对任何可能的 r 都这样做，这意味着我对 r 本身一无所知，包括如何构造它的值。而我唯一可用的就是你给我的函数a -> r。调用此类函数的唯一方法是给它一个 a.
也就是说，如果我做出这样的承诺，我一定已经暗中有了一个a。
对于更正式的解释，回想一下 "isomorphic" 的直白意思是 "can be unambiguously converted back and forth without losses"。这就是基数论点的意思：如果你有相同数量的东西，你总是可以在它们之间安排一个配对。
并且在您的问题中您已经显示了两种转换：cont 转换一种方式，unCont 转换另一种方式。你可以简单地证明 cont . unCont = unCont . cont = id。因此类型是同构的。
虽然显示这两种转换的存在更为正式，但我发现通过直觉了解这两种类型的真实情况并不总是令人满意"kinda the same thing"，因此我在上面给出了直观的解释。
存在多态类型时无法真正定义基数。现在可以理解，多态类型 "are not sets" 正如人们最初想象的那样。雷诺兹在他的论文 "Polymorphism is not set theoretic" 中提供了一个著名的开创性论证，证明我们不能简单地以 "trivial" 方式解释集合类型并获得有意义的概念。
确实，在集合中 2^K 和 K 是不同的基数，第一个更大。同样，2^(2^K) 大于 K。然而，F X = 2^(2^X)（类似于F a = (a -> Bool) -> Bool）形成一个（协变）函子，我们可以找到一个不动点
newtype T = T ((T -> Bool) -> Bool)
获得 T 与 2^(2^T) 同构，这在集合中没有意义，正是因为它们不能具有相同的基数。
（即使没有递归类型，在多态性存在的情况下，通过编码为forall a. (F a -> a) -> a，也可以获得上面的类型T。）
无论如何，要解决这个僵局，我们需要将 a -> Bool 解释为不同于函数集 2^a 的其他东西。一种可能的解决方案是使用 Scott 连续函数，正如 Scott 所做的那样。一个相关的解决方案是使用 stable functions（参见 Girard 的 "Proofs and types" 书），它（如果我没记错的话）解释了 T 和 T -> Bool具有 相同的 基数（除非两者都是有限的）。
因此，在多态类型存在的情况下，基数不是用于检查类型同构的正确工具。我们真的需要看看是否有可能像您在问题中发布的那样制作同构函数及其反函数。
在书Thinking with Types中，6.4 Continuation Monad说类型a和forall r. (a -> r) -> r是同构的，可以通过以下函数证明：
cont :: a -> (forall r. (a -> r) -> r)
cont x = \f -> f x
unCont :: (forall r. (a -> r) -> r) -> a
unCont f = f id
在这本书中，它告诉我们具有相同基数的任何两个类型总是彼此同构的。所以我试图找出类型的基数a 和 forall r. (a -> r) -> r.
假设 a 类型的基数是 |a|。那么对于类型forall r. (a -> r) -> r，如何计算出它的基数等于|a|呢？函数类型 a -> b 的基数为 |b|^|a|，即 |b| 的 |a| 次方，因此 forall r. (a -> r) -> r 的基数为 |r|^(|r|^|a|)。怎么可能等于|a|？
我很困惑。感谢您的任何提示！
基数参数实际上不适用于多态类型（请参阅@chi 的回答）。
但是同构本身可以这样直观地解释：
类型 forall r. (a -> r) -> r 表示“如果你给我一个将 a 转换为 r 的函数，我可以还给你一个 r . 哦，我可以为任何可能的 r 做到这一点 "
要实现这样的承诺，唯一的办法就是偷偷地把a拿在手上。
由于我承诺对任何可能的 r 都这样做，这意味着我对 r 本身一无所知，包括如何构造它的值。而我唯一可用的就是你给我的函数a -> r。调用此类函数的唯一方法是给它一个 a.
也就是说，如果我做出这样的承诺，我一定已经暗中有了一个a。
对于更正式的解释，回想一下 "isomorphic" 的直白意思是 "can be unambiguously converted back and forth without losses"。这就是基数论点的意思：如果你有相同数量的东西，你总是可以在它们之间安排一个配对。
并且在您的问题中您已经显示了两种转换：cont 转换一种方式，unCont 转换另一种方式。你可以简单地证明 cont . unCont = unCont . cont = id。因此类型是同构的。
虽然显示这两种转换的存在更为正式，但我发现通过直觉了解这两种类型的真实情况并不总是令人满意"kinda the same thing"，因此我在上面给出了直观的解释。
存在多态类型时无法真正定义基数。现在可以理解，多态类型 "are not sets" 正如人们最初想象的那样。雷诺兹在他的论文 "Polymorphism is not set theoretic" 中提供了一个著名的开创性论证，证明我们不能简单地以 "trivial" 方式解释集合类型并获得有意义的概念。
确实，在集合中 2^K 和 K 是不同的基数，第一个更大。同样，2^(2^K) 大于 K。然而，F X = 2^(2^X)（类似于F a = (a -> Bool) -> Bool）形成一个（协变）函子，我们可以找到一个不动点
newtype T = T ((T -> Bool) -> Bool)
获得 T 与 2^(2^T) 同构，这在集合中没有意义，正是因为它们不能具有相同的基数。
（即使没有递归类型，在多态性存在的情况下，通过编码为forall a. (F a -> a) -> a，也可以获得上面的类型T。）
无论如何，要解决这个僵局，我们需要将 a -> Bool 解释为不同于函数集 2^a 的其他东西。一种可能的解决方案是使用 Scott 连续函数，正如 Scott 所做的那样。一个相关的解决方案是使用 stable functions（参见 Girard 的 "Proofs and types" 书），它（如果我没记错的话）解释了 T 和 T -> Bool具有 相同的 基数（除非两者都是有限的）。
因此，在多态类型存在的情况下，基数不是用于检查类型同构的正确工具。我们真的需要看看是否有可能像您在问题中发布的那样制作同构函数及其反函数。