为什么这段使用 UndecidableInstances 的代码会编译，然后生成运行时无限循环？
Why does this code using UndecidableInstances compile, then generate a runtime infinite loop?
之前使用 UndecidableInstances 编写代码时，我 运行 发现了一些我觉得很奇怪的东西。我设法无意中创建了一些我认为不应该进行类型检查的代码：
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE UndecidableInstances #-}
data Foo = Foo
class ConvertFoo a b where
convertFoo :: a -> b
instance (ConvertFoo a Foo, ConvertFoo Foo b) => ConvertFoo a b where
convertFoo = convertFoo . (convertFoo :: a -> Foo)
evil :: Int -> String
evil = convertFoo
具体来说，convertFoo 函数在给定 any 输入时进行类型检查以生成 any 输出，如 evil 函数。起初，我认为也许我不小心实现了 unsafeCoerce，但事实并非如此：实际上是在尝试调用我的 convertFoo 函数（例如，通过执行类似 evil 3 的操作）只是进入了一个无限循环。
我有点模糊地理解发生了什么。我对这个问题的理解是这样的：
- 我定义的
ConvertFoo 实例适用于 任何 输入和输出，a 和 b，仅受限于a -> Foo 和 Foo -> b. 中转换函数必须存在的两个附加约束
- 不知何故，该定义能够匹配任何输入和输出类型，因此似乎对
convertFoo :: a -> Foo 的调用正在选择 convertFoo 本身的定义，因为它是唯一的反正有空
- 由于
convertFoo无限调用自身，函数进入了一个永不终止的无限循环。
- 因为
convertFoo 永远不会终止，该定义的类型是 bottom，所以 技术上 none 类型是曾经被违反的，并且程序类型检查.
现在，即使上面的理解是正确的，我仍然对整个程序为什么要进行类型检查感到困惑。具体来说，我预计 ConvertFoo a Foo 和 ConvertFoo Foo b 约束会失败，因为不存在此类实例。
我确实理解（至少是模糊地）在选择一个实例时约束并不重要——只根据实例头选择实例，然后检查约束——所以我可以看到，由于我的 ConvertFoo a b 实例，这些约束可能会很好地解决，它尽可能地宽松。然而，这将需要解决相同的约束集，我认为这会使类型检查器陷入无限循环，导致 GHC 要么挂在编译上，要么给我一个堆栈溢出错误（后者我见过之前）。
不过，很明显，类型检查器确实 而不是 循环，因为它愉快地触底并愉快地编译我的代码。为什么？在此特定示例中如何满足实例上下文？为什么这不会给我类型错误或产生类型检查循环？
我完全同意这是一个很好的问题。它讲述了如何
我们对类型classes 的直觉与现实不同。
类型class惊喜
要看看这里发生了什么，要提高赌注
evil 的类型签名：
data X
class Convert a b where
convert :: a -> b
instance (Convert a X, Convert X b) => Convert a b where
convert = convert . (convert :: a -> X)
evil :: a -> b
evil = convert
显然选择了 Covert a b 实例，因为只有
class 的一个实例。类型检查器在想类似的东西
这个：
Convert a X 为真，如果...
Convert a X 为真 [假设为真]- 和
Convert X X为真
Convert X X 为真，如果...
Convert X X 为真 [假设为真]Convert X X 为真 [假设为真]
Convert X b 为真，如果...
Convert X X 为真 [从上面为真]- 和
Convert X b 为真 [假设为真]
类型检查器让我们大吃一惊。我们不希望 Convert X X
true 因为我们没有定义类似的东西。但是 (Convert X X, Convert X X) => Convert X X 是一种重言式：它是
自动为真，无论在 class.
中定义了什么方法，它都是真的
这可能不符合我们class类型的心理模型。我们期望
编译器在这一点上呆呆地抱怨 Convert X X
不可能是真的，因为我们没有为它定义任何实例。我们期待
编译器站在 Convert X X，寻找另一个位置
走到 Convert X X 为真的地方，然后放弃，因为那里
没有其他地方是这样的。但是编译器能够
递归！递归，循环，图灵完备
我们为类型检查器赋予了这种能力，我们做到了
UndecidableInstances。当文档说明它是
可以将编译器发送到循环中很容易假设
最糟糕的是，我们假设坏循环总是无限循环。但
在这里我们演示了一个更致命的循环，一个循环
终止——除了以一种令人惊讶的方式。
（这一点在 Daniel 的评论中表现得更为明显：
class Loop a where
loop :: a
instance Loop a => Loop a where
loop = loop
.)
不确定性的危险
这正是 UndecidableInstances
允许。如果我们关闭该扩展程序并打开 FlexibleContexts
（本质上只是句法的无害扩展），我们得到
关于违反 Paterson 之一的警告
条件:
...
Constraint is no smaller than the instance head
in the constraint: Convert a X
(Use UndecidableInstances to permit this)
In the instance declaration for ‘Convert a b’
...
Constraint is no smaller than the instance head
in the constraint: Convert X b
(Use UndecidableInstances to permit this)
In the instance declaration for ‘Convert a b’
"No smaller than instance head," 虽然我们可以在心里重写它
因为“这个实例可能会被用来证明一个断言
本身并导致你非常痛苦、咬牙切齿和打字。”
Paterson 条件一起防止实例解析中的循环。
我们在这里的违规行为证明了为什么它们是必要的，我们可以
大概查阅一些论文，看看为什么它们足够了。
触底反弹
至于程序为什么会在运行时死循环：还有就是无聊
答案，其中 evil :: a -> b 只能无限循环或抛出一个
例外或通常触底反弹，因为我们信任 Haskell
typechecker 并且没有可以居住的值 a -> b 除了
底.
一个更有趣的答案是，因为 Convert X X 是
同义反复，它的实例定义是这个无限循环
convertXX :: X -> X
convertXX = convertXX . convertXX
我们可以类似地展开 Convert A B 实例定义。
convertAB :: A -> B
convertAB =
convertXB . convertAX
where
convertAX = convertXX . convertAX
convertXX = convertXX . convertXX
convertXB = convertXB . convertXX
这种令人惊讶的行为，以及如何限制实例解析（通过
默认没有扩展名）是为了避免这些
行为，也许可以作为 Haskell 的一个很好的理由
typeclass 系统尚未得到广泛采用。尽管其
令人印象深刻的人气和力量，它有奇怪的角落（无论是
它在文档或错误消息或语法中，甚至可能在
它的基本逻辑）似乎特别不适合我们人类
考虑类型级抽象。
以下是我在心理上处理这些案例的方式：
class ConvertFoo a b where convertFoo :: a -> b
instance (ConvertFoo a Foo, ConvertFoo Foo b) => ConvertFoo a b where
convertFoo = ...
evil :: Int -> String
evil = convertFoo
首先，我们从计算所需实例集开始。
evil 直接要求 ConvertFoo Int String (1).- 那么，(1) 需要
ConvertFoo Int Foo (2) 和 ConvertFoo Foo String (3)。
- 然后，(2) 需要
ConvertFoo Int Foo（我们已经算过了）和 ConvertFoo Foo Foo (4).
- 那么 (3) 需要
ConvertFoo Foo Foo（计数）和 ConvertFoo Foo String（计数）。
- 那么 (4) 需要
ConvertFoo Foo Foo（计数）和 ConvertFoo Foo Foo（计数）。
因此，我们到达了一个固定点，这是一组有限的所需实例。编译器在有限时间内计算集合没有问题：只需应用实例定义，直到不需要更多约束。
然后，我们继续为这些实例提供代码。在这里。
convertFoo_1 :: Int -> String
convertFoo_1 = convertFoo_3 . convertFoo_2
convertFoo_2 :: Int -> Foo
convertFoo_2 = convertFoo_4 . convertFoo_2
convertFoo_3 :: Foo -> String
convertFoo_3 = convertFoo_3 . convertFoo_4
convertFoo_4 :: Foo -> Foo
convertFoo_4 = convertFoo_4 . convertFoo_4
我们得到了一堆相互递归的实例定义。在这种情况下，这些将在运行时循环，但没有理由在编译时拒绝它们。
之前使用 UndecidableInstances 编写代码时，我 运行 发现了一些我觉得很奇怪的东西。我设法无意中创建了一些我认为不应该进行类型检查的代码：
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE UndecidableInstances #-}
data Foo = Foo
class ConvertFoo a b where
convertFoo :: a -> b
instance (ConvertFoo a Foo, ConvertFoo Foo b) => ConvertFoo a b where
convertFoo = convertFoo . (convertFoo :: a -> Foo)
evil :: Int -> String
evil = convertFoo
具体来说，convertFoo 函数在给定 any 输入时进行类型检查以生成 any 输出，如 evil 函数。起初，我认为也许我不小心实现了 unsafeCoerce，但事实并非如此：实际上是在尝试调用我的 convertFoo 函数（例如，通过执行类似 evil 3 的操作）只是进入了一个无限循环。
我有点模糊地理解发生了什么。我对这个问题的理解是这样的：
- 我定义的
ConvertFoo实例适用于 任何 输入和输出，a和b，仅受限于a -> Foo和Foo -> b. 中转换函数必须存在的两个附加约束
- 不知何故，该定义能够匹配任何输入和输出类型，因此似乎对
convertFoo :: a -> Foo的调用正在选择convertFoo本身的定义，因为它是唯一的反正有空 - 由于
convertFoo无限调用自身，函数进入了一个永不终止的无限循环。 - 因为
convertFoo永远不会终止，该定义的类型是 bottom，所以 技术上 none 类型是曾经被违反的，并且程序类型检查.
现在，即使上面的理解是正确的，我仍然对整个程序为什么要进行类型检查感到困惑。具体来说，我预计 ConvertFoo a Foo 和 ConvertFoo Foo b 约束会失败，因为不存在此类实例。
我确实理解（至少是模糊地）在选择一个实例时约束并不重要——只根据实例头选择实例，然后检查约束——所以我可以看到，由于我的 ConvertFoo a b 实例，这些约束可能会很好地解决，它尽可能地宽松。然而，这将需要解决相同的约束集，我认为这会使类型检查器陷入无限循环，导致 GHC 要么挂在编译上，要么给我一个堆栈溢出错误（后者我见过之前）。
不过，很明显，类型检查器确实 而不是 循环，因为它愉快地触底并愉快地编译我的代码。为什么？在此特定示例中如何满足实例上下文？为什么这不会给我类型错误或产生类型检查循环？
我完全同意这是一个很好的问题。它讲述了如何 我们对类型classes 的直觉与现实不同。
类型class惊喜
要看看这里发生了什么，要提高赌注
evil 的类型签名：
data X
class Convert a b where
convert :: a -> b
instance (Convert a X, Convert X b) => Convert a b where
convert = convert . (convert :: a -> X)
evil :: a -> b
evil = convert
显然选择了 Covert a b 实例，因为只有
class 的一个实例。类型检查器在想类似的东西
这个：
Convert a X为真，如果...Convert a X为真 [假设为真]- 和
Convert X X为真Convert X X为真，如果...Convert X X为真 [假设为真]Convert X X为真 [假设为真]
Convert X b为真，如果...Convert X X为真 [从上面为真]- 和
Convert X b为真 [假设为真]
类型检查器让我们大吃一惊。我们不希望 Convert X X
true 因为我们没有定义类似的东西。但是 (Convert X X, Convert X X) => Convert X X 是一种重言式：它是
自动为真，无论在 class.
这可能不符合我们class类型的心理模型。我们期望
编译器在这一点上呆呆地抱怨 Convert X X
不可能是真的，因为我们没有为它定义任何实例。我们期待
编译器站在 Convert X X，寻找另一个位置
走到 Convert X X 为真的地方，然后放弃，因为那里
没有其他地方是这样的。但是编译器能够
递归！递归，循环，图灵完备
我们为类型检查器赋予了这种能力，我们做到了
UndecidableInstances。当文档说明它是
可以将编译器发送到循环中很容易假设
最糟糕的是，我们假设坏循环总是无限循环。但
在这里我们演示了一个更致命的循环，一个循环
终止——除了以一种令人惊讶的方式。
（这一点在 Daniel 的评论中表现得更为明显：
class Loop a where
loop :: a
instance Loop a => Loop a where
loop = loop
.)
不确定性的危险
这正是 UndecidableInstances
允许。如果我们关闭该扩展程序并打开 FlexibleContexts
（本质上只是句法的无害扩展），我们得到
关于违反 Paterson 之一的警告
条件:
...
Constraint is no smaller than the instance head
in the constraint: Convert a X
(Use UndecidableInstances to permit this)
In the instance declaration for ‘Convert a b’
...
Constraint is no smaller than the instance head
in the constraint: Convert X b
(Use UndecidableInstances to permit this)
In the instance declaration for ‘Convert a b’
"No smaller than instance head," 虽然我们可以在心里重写它 因为“这个实例可能会被用来证明一个断言 本身并导致你非常痛苦、咬牙切齿和打字。” Paterson 条件一起防止实例解析中的循环。 我们在这里的违规行为证明了为什么它们是必要的，我们可以 大概查阅一些论文，看看为什么它们足够了。
触底反弹
至于程序为什么会在运行时死循环：还有就是无聊
答案，其中 evil :: a -> b 只能无限循环或抛出一个
例外或通常触底反弹，因为我们信任 Haskell
typechecker 并且没有可以居住的值 a -> b 除了
底.
一个更有趣的答案是，因为 Convert X X 是
同义反复，它的实例定义是这个无限循环
convertXX :: X -> X
convertXX = convertXX . convertXX
我们可以类似地展开 Convert A B 实例定义。
convertAB :: A -> B
convertAB =
convertXB . convertAX
where
convertAX = convertXX . convertAX
convertXX = convertXX . convertXX
convertXB = convertXB . convertXX
这种令人惊讶的行为，以及如何限制实例解析（通过 默认没有扩展名）是为了避免这些 行为，也许可以作为 Haskell 的一个很好的理由 typeclass 系统尚未得到广泛采用。尽管其 令人印象深刻的人气和力量，它有奇怪的角落（无论是 它在文档或错误消息或语法中，甚至可能在 它的基本逻辑）似乎特别不适合我们人类 考虑类型级抽象。
以下是我在心理上处理这些案例的方式：
class ConvertFoo a b where convertFoo :: a -> b
instance (ConvertFoo a Foo, ConvertFoo Foo b) => ConvertFoo a b where
convertFoo = ...
evil :: Int -> String
evil = convertFoo
首先，我们从计算所需实例集开始。
evil直接要求ConvertFoo Int String(1).- 那么，(1) 需要
ConvertFoo Int Foo(2) 和ConvertFoo Foo String(3)。 - 然后，(2) 需要
ConvertFoo Int Foo（我们已经算过了）和ConvertFoo Foo Foo(4). - 那么 (3) 需要
ConvertFoo Foo Foo（计数）和ConvertFoo Foo String（计数）。 - 那么 (4) 需要
ConvertFoo Foo Foo（计数）和ConvertFoo Foo Foo（计数）。
因此，我们到达了一个固定点，这是一组有限的所需实例。编译器在有限时间内计算集合没有问题：只需应用实例定义，直到不需要更多约束。
然后，我们继续为这些实例提供代码。在这里。
convertFoo_1 :: Int -> String
convertFoo_1 = convertFoo_3 . convertFoo_2
convertFoo_2 :: Int -> Foo
convertFoo_2 = convertFoo_4 . convertFoo_2
convertFoo_3 :: Foo -> String
convertFoo_3 = convertFoo_3 . convertFoo_4
convertFoo_4 :: Foo -> Foo
convertFoo_4 = convertFoo_4 . convertFoo_4
我们得到了一堆相互递归的实例定义。在这种情况下，这些将在运行时循环，但没有理由在编译时拒绝它们。