为什么 Haskell 变量在通过模式匹配绑定时不是多态的？

Question

考虑在模式中引入的变量，例如 Haskell 示例中的 f：

case (\x -> x) of f -> (f True, f 'c')

由于 f 的两种不同用法，此代码导致类型错误 ("Couldn't match expected type ‘Bool’ with actual type ‘Char’")。它表明 f 的推断类型在 Haskell.

中不是多态的

但是为什么 f 不能是多态的呢？

我有两点比较：OCaml和"textbook"Hindley-Milner。两者都表明 f 应该是多态的。

在OCaml中，类似的代码不是错误：
```
match (fun x -> x) with f -> (f true, f 'c')
```
计算结果为 (true, 'c')，类型为 bool * char。所以看起来 OCaml 与分配 f 多态类型相处得很好。
我们可以通过将事情分解为 Hindley-Milner 的基础知识来获得清晰度 - "let" 的 lambda 演算 - Haskell 和 OCaml 都基于它。归结到这个核心系统，当然就没有模式匹配这回事了。不过，我们可以画出相似之处。在 "let" 和 "lambda" 之间，case expr1 of f -> expr2 比 (lambda f. expr2) expr1 更接近 let f = expr1 in expr2。 "Case"，就像 "let"，语法上限制 f 绑定到 expr1，而函数 lambda f. expr2 不知道 f 会是什么绑定到，因为该函数对在程序中调用它的位置没有这样的限制。这就是为什么 let 绑定变量在 Hindley-Milner 中被泛化而 lambda 绑定变量不是的原因。看起来允许泛化 let-bound 变量的相同推理表明模式匹配引入的变量也可以被泛化。

为了清楚起见，上面的例子是最小的，所以它们只展示了模式匹配中的一个微不足道的模式 f，但是所有相同的逻辑都扩展到任意复杂的模式，如 Just (a:b:(x,y):_)，这可以引入多个变量都将被概括。

我的分析正确吗？特别是在 Haskell 中 - 认识到它不仅仅是普通的 Hindley-Milner 而不是 OCaml - 为什么我们不在第一个示例中概括 f 的类型？

这是一个明确的语言设计决定吗？如果是，原因是什么？（我注意到 some in the community think that not even "let" should be generalized，但我认为设计决策早于该论文。）

如果模式中引入的变量类似于 "let" 的多态性，是否会严重破坏与 Haskell 其他方面的兼容性？

Answer 1

第一个问题是类型类，泛化并不总是免费的。考虑 show :: forall a. Show a => a -> String 和这个表达式：

case show of
  f -> ...

如果您将 f 泛化为 f :: forall a. Show a => a -> String，那么 GHC 将在每次调用 f 时传递一个 Show 字典，而不是在 f 的单次出现时传递一次=17=]。如果有多个调用都是同一类型，与不概括相比，这种重复工作。

当与类型类结合使用时，它实际上也不是当前类型推断算法的泛化：它可能导致现有程序不再进行类型检查。例如，

    case show of
      f -> f () ++ f mempty

通过不概括 f，我们可以推断 mempty 具有类型 ()。另一方面，泛化 f :: forall a. Show a => a -> String 将失去这种联系，并且该表达式中 mempty 的类型将是不明确的。

虽然这些都是小问题，但即使不完全向后兼容，也许在一些单态限制下一切都会好起来。

Answer 2

如果我们将一个多态类型 (forall x. t) 分配给一个案例审查者，那么它不匹配任何非平凡的模式，所以 case.

没有意义

我们可以用其他有用的方式概括吗？不是真的，因为 GHC 不支持 "impredicative" 实例化。在您的 Just (a:b:(x,y):_) 示例中，没有一个绑定变量可以具有多态类型，因为 Maybe、(,) 和 [] 无法使用此类类型进行实例化。

有一点可行，正如评论中提到的：具有多态字段的数据类型，例如data Endo = Endo (forall a. a -> a)。但是，多态字段的类型检查在技术上并不涉及泛化步骤，其行为也不像 let-generalization。

原则上，泛化可以在很多点进行，例如甚至在任意函数参数处（例如 f (\x -> x)）。然而，过多的泛化会引入难以处理的高阶类型，从而阻碍类型推断；这也可以理解为通过删除未解决的元变量来消除程序不同部分之间有用的类型依赖性。尽管有些系统可以比 GHC 更好地处理更高级别的推理，最著名的是 MLF，但它们也复杂得多并且没有太多实际用途。我个人更喜欢根本不使用 silent let-generalization。

Answer 3

除了其他答案之外，就与存在类型的交互而言，在模式匹配中如何处理类型变量是有原因的。让我们看一下 Data.Functor.Coyoneda:

中的几个定义

{-# LANGUAGE GADTs #-}

data Coyoneda f a where
    Coyoneda :: (b -> a) -> f b -> Coyoneda f a

lowerCoyoneda :: Functor f => Coyoneda f a -> f a
lowerCoyoneda (Coyoneda g x) = fmap g x

Coyoneda 具有构造函数的两个参数都使用的存在类型变量。如果 GHC 没有确定该类型，则 lowerCoyoneda 中的 fmap 无法进行类型检查。 GHC 需要知道 g 和 x 在它们的类型中有适当的关系，这需要在模式匹配中修复类型变量。

为什么 Haskell 变量在通过模式匹配绑定时不是多态的？

Why aren't Haskell variables polymorphic when bound by pattern matching?

ocaml

haskell

type-inference