types - 函数式语言是否使用来自调用者的信息来进行类型推断？

Question

考虑例如 Haskell 或 ML 中的函数 f1 和 f2。假设 f2 调用 f1。类型推断是否只是使用 f1 可以调用的信息，相当于只看 f1 的定义。或者它是否还查看了 f2 在对 f1 进行类型推断时如何调用 f1。例如 f2 在调用 f1 时可能会传入文字，这将限制 f1 的参数类型。

Answer 1

这取决于函数f1是由声明绑定还是通过其他方式绑定（例如，作为 的函数参数f2）。在前一种情况下，它的类型可以泛化为多态，在后一种情况下则不能，未解析的部分由上下文决定。即使在前一种情况下，也可能适用其他规则，例如 ML 的值限制。

考虑 Haskell 中的这个例子：

f1 = \x -> x  -- polymorphic: f1 :: a -> a
f2 = f1 True  -- instantiates f1 :: Bool -> Bool

f2 = let f1 = \x -> x in f1 True  -- likewise

f2 = (\f1 -> f1 True) (\x -> x)  -- here, f1 cannot be polymorphic,
                                 -- so the lambda is restricted to Bool -> Bool by the call

同样在 SML 中：

val f1 = fn x => x  (* polymorphic, f1 : 'a -> 'a *)
val f2 = f1 true

val f2 = let val f1 = fn x => x in f1 true end  (* likewise *)

val f2 = (fn f1 => f1 true) (fn x => x)  (* f1 monomorphic, f1 : bool -> bool *)

val f1 = let _ = 0 in fn x => x end  (* value restriction applies, f1 cannot be polymorphic *)
val f2 = f1 true  (* determines type f1 : bool -> bool *)

为了清楚起见，我在这里没有使用缩写的函数声明语法。

Answer 2

类型系统不使用有关调用者的信息来确定函数可以处理的类型——这既过于限制又通常不可能实现。例如，假设 (Haskell)

aList :: [Int]
aList = [1,2,3]

one = head aList

今后将限制headfrom [a] -> ato的类型[Int] -> Int；之后，head ["hello", "world"]这是不可能head的，下次我们想在不同的类型上使用它时，我们必须重新定义。但是，在定义的上下文one中，head实际上具有类型[Int] -> Int，因为其类型中的变量被实例化。但这不会改变其全局定义head或其类型。

（在实践中，编译器可以专门化一个它知道将在少数情况下调用的函数，并使代码适应传入的特定类型，只要它不改变程序语义。）