Haskell 如何对无限递归值进行类型检查？
How does Haskell type-check infinite recursive values?
定义此数据类型：
data NaturalNumber = Zero | S NaturalNumber
deriving (Show)
在 Haskell（使用 GHC 编译）中，此代码将 运行 没有警告或错误：
infinity = S infinity
inf1 = S inf2
inf2 = S inf1
所以递归和相互递归无限深的值都通过了类型检查。
但是下面的代码报错：
j = S 'h'
错误状态 Couldn't match expected type ‘NaturalNumber’ with actual type 'Char'。即使我设置
，（相同的）错误仍然存在
j = S (S (S (S ... (S 'h')...)))
有一百个左右的嵌套 S。
Haskell 如何判断 infinity 是 NaturalNumber 的有效成员而 j 不是？
有趣的是，它还允许：
bottom = bottom
k = S bottom
是否 Haskell 只是试图证明程序的不正确性，如果失败则允许它？还是 Haskell 的类型系统不是图灵完备的，所以如果它允许该程序，那么该程序可证明（在类型级别）是正确的？
（如果类型系统（在 Haskell 的形式语义中，而不仅仅是类型检查器）是图灵完备的，那么它要么无法意识到一些正确类型的程序是正确的，要么一些错误类型的程序由于停机问题的不确定性，程序不正确。）
嗯
S :: NaturalNumber -> NaturalNumber
在
infinity = S infinity
我们从什么都不假设开始：我们分配 infinity 一些未解决的类型 _a 并试图找出它是什么。我们知道我们已经将 S 应用于 infinity，因此 _a 必须是构造函数类型中箭头左侧的任何内容，即 NaturalNumber。我们知道 infinity 是 S 的应用结果，所以 infinity :: NaturalNumber，再次（如果我们为这个定义得到两个冲突的类型，我们将不得不发出类型错误） .
类似的推理适用于相互递归的定义。 inf1 必须是 NaturalNumber 因为它在 inf2 中作为 S 的参数出现； inf2 必须是 NaturalNumber 因为它是 S 的结果；等等
一般算法是分配未知类型的定义（值得注意的例外是文字和构造函数），然后通过查看每个定义的使用方式来创建对这些类型的约束。例如。这一定是某种形式的列表，因为它是 reversed，而且这一定是一个 Int，因为它被用来从 IntMap 等中查找值
如
oops = S 'a'
'a' :: Char 因为它是一个文字，但是，我们也必须有 'a' :: NaturalNumber 因为它被用作 S 的参数。我们得到了明显的虚假约束，即文字的类型必须同时为 Char 和 NaturalNumber，这会导致类型错误。
并在
bottom = bottom
我们从 bottom :: _a 开始。唯一的约束是 _a ~ _a，因为类型 _a (bottom) 的值被用于预期类型 _a 的值（在bottom)。由于没有什么可以进一步限制类型，未解决的类型变量是 广义 ：它被通用量词绑定以产生 bottom :: forall a. a.
请注意，在推断 bottom 的类型时，上面的 bottom 的两种用法具有相同的类型 (_a)。这打破了多态递归：在其定义中每次出现的值都被认为是与定义本身相同的类型。例如
-- perfectly balanced binary trees
data Binary a = Leaf a | Branch (Binary (a, a))
-- headB :: _a -> _r
headB (Leaf x) = x -- _a ~ Binary _r; headB :: Binary _r -> _r
headB (Branch bin) = fst (headB bin)
-- recursive call has type headB :: Binary _r -> _r
-- but bin :: Binary (_r, _r); mismatch
所以你需要一个类型签名：
headB :: {-forall a.-} Binary a -> a
headB (Leaf x) = x
headB (Branch bin) = fst (headB {-@(a, a)-} bin)
-- knowing exactly what headB's signature is allows for polymorphic recursion
所以：当某些东西没有类型签名时，类型检查器会尝试为其分配一个类型，如果它在途中遇到虚假约束，它会拒绝该程序。当某物具有类型签名时，类型检查器会深入其中以确保它是正确的（尝试证明它是错误的，如果你喜欢那样想的话）。
Haskell 的类型系统不是图灵完备的，因为有严格的句法限制来防止例如键入 lambdas（没有语言扩展），但它不足以确保所有程序 运行 无错误地完成，因为它仍然允许底部（更不用说所有不安全的函数）。它提供了较弱的保证，即如果程序在不使用不安全函数的情况下运行到完成，它将保持 type-correct。在 GHC 下，通过足够的语言扩展，类型系统确实变得图灵完备。我认为它不允许 ill-typed 程序通过；我认为你最多能做的就是让编译器陷入无限循环。
定义此数据类型：
data NaturalNumber = Zero | S NaturalNumber
deriving (Show)
在 Haskell（使用 GHC 编译）中，此代码将 运行 没有警告或错误：
infinity = S infinity
inf1 = S inf2
inf2 = S inf1
所以递归和相互递归无限深的值都通过了类型检查。
但是下面的代码报错：
j = S 'h'
错误状态 Couldn't match expected type ‘NaturalNumber’ with actual type 'Char'。即使我设置
j = S (S (S (S ... (S 'h')...)))
有一百个左右的嵌套 S。
Haskell 如何判断 infinity 是 NaturalNumber 的有效成员而 j 不是？
有趣的是，它还允许：
bottom = bottom
k = S bottom
是否 Haskell 只是试图证明程序的不正确性，如果失败则允许它？还是 Haskell 的类型系统不是图灵完备的，所以如果它允许该程序，那么该程序可证明（在类型级别）是正确的？
（如果类型系统（在 Haskell 的形式语义中，而不仅仅是类型检查器）是图灵完备的，那么它要么无法意识到一些正确类型的程序是正确的，要么一些错误类型的程序由于停机问题的不确定性，程序不正确。）
嗯
S :: NaturalNumber -> NaturalNumber
在
infinity = S infinity
我们从什么都不假设开始：我们分配 infinity 一些未解决的类型 _a 并试图找出它是什么。我们知道我们已经将 S 应用于 infinity，因此 _a 必须是构造函数类型中箭头左侧的任何内容，即 NaturalNumber。我们知道 infinity 是 S 的应用结果，所以 infinity :: NaturalNumber，再次（如果我们为这个定义得到两个冲突的类型，我们将不得不发出类型错误） .
类似的推理适用于相互递归的定义。 inf1 必须是 NaturalNumber 因为它在 inf2 中作为 S 的参数出现； inf2 必须是 NaturalNumber 因为它是 S 的结果；等等
一般算法是分配未知类型的定义（值得注意的例外是文字和构造函数），然后通过查看每个定义的使用方式来创建对这些类型的约束。例如。这一定是某种形式的列表，因为它是 reversed，而且这一定是一个 Int，因为它被用来从 IntMap 等中查找值
如
oops = S 'a'
'a' :: Char 因为它是一个文字，但是，我们也必须有 'a' :: NaturalNumber 因为它被用作 S 的参数。我们得到了明显的虚假约束，即文字的类型必须同时为 Char 和 NaturalNumber，这会导致类型错误。
并在
bottom = bottom
我们从 bottom :: _a 开始。唯一的约束是 _a ~ _a，因为类型 _a (bottom) 的值被用于预期类型 _a 的值（在bottom)。由于没有什么可以进一步限制类型，未解决的类型变量是 广义 ：它被通用量词绑定以产生 bottom :: forall a. a.
请注意，在推断 bottom 的类型时，上面的 bottom 的两种用法具有相同的类型 (_a)。这打破了多态递归：在其定义中每次出现的值都被认为是与定义本身相同的类型。例如
-- perfectly balanced binary trees
data Binary a = Leaf a | Branch (Binary (a, a))
-- headB :: _a -> _r
headB (Leaf x) = x -- _a ~ Binary _r; headB :: Binary _r -> _r
headB (Branch bin) = fst (headB bin)
-- recursive call has type headB :: Binary _r -> _r
-- but bin :: Binary (_r, _r); mismatch
所以你需要一个类型签名：
headB :: {-forall a.-} Binary a -> a
headB (Leaf x) = x
headB (Branch bin) = fst (headB {-@(a, a)-} bin)
-- knowing exactly what headB's signature is allows for polymorphic recursion
所以：当某些东西没有类型签名时，类型检查器会尝试为其分配一个类型，如果它在途中遇到虚假约束，它会拒绝该程序。当某物具有类型签名时，类型检查器会深入其中以确保它是正确的（尝试证明它是错误的，如果你喜欢那样想的话）。
Haskell 的类型系统不是图灵完备的，因为有严格的句法限制来防止例如键入 lambdas（没有语言扩展），但它不足以确保所有程序 运行 无错误地完成，因为它仍然允许底部（更不用说所有不安全的函数）。它提供了较弱的保证，即如果程序在不使用不安全函数的情况下运行到完成，它将保持 type-correct。在 GHC 下，通过足够的语言扩展，类型系统确实变得图灵完备。我认为它不允许 ill-typed 程序通过；我认为你最多能做的就是让编译器陷入无限循环。