在 OCaml 中,`'a.` 和 `type a.` 之间有什么区别以及何时使用它们?

In OCaml, what is the difference between `'a.` and `type a.` and when to use each?

OCaml 有几种不同的多态类型注释语法:

let f :         'a -> 'a = … (* Isn’t this one already polymorphic? (answer: NO) *)
let f : 'a.     'a -> 'a = …
let f : type a.  a ->  a = …

我们经常在使用花哨的代数数据类型(通常是 GADT)时看到它们,而它们似乎是必要的。

这些语法有什么区别?何时以及为何必须使用每一个?

我将使用以下代码(取自)作为运行示例。在这里,reduce 定义上的类型注释实际上是需要进行类型检查的。

(* The type [('a, 'c) fun_chain] represents a chainable list of functions, i.e.
 * such that the output type of one function is the input type of the next one;
 * ['a] and ['c] are the input and output types of the whole chain.
 * This is implemented as a recursive GADT (generalized algebraic data type). *)
type (_, _) fun_chain =
  | Nil  : ('a, 'a) fun_chain
  | Cons : ('a -> 'b) * ('b, 'c) fun_chain -> ('a, 'c) fun_chain

(* [reduce] reduces a chain to just one function by composing all
 * functions of the chain. *)
let rec reduce : type a c. (a, c) fun_chain -> a -> c =
  fun chain x ->
    begin match chain with
    | Nil              -> x
    | Cons (f, chain') -> reduce chain' (f x)
    end

很短的故事

在 let 定义上,像 : 'a -> 'a 这样的注释不会强制 多态性(语法是误导性的,因为 val 声明上的相同注释即在模块签名 确实 强制执行多态性)。

: type a. … is a type annotation with explicit (forced) polymorphism. You can think of this as the universal quantifier: ∀ a, …. In the code above we make use of advanced features of the type system, namely, polymorphic recursion and branches with different types,这让类型推断无所适从。为了在这种情况下进行程序类型检查,我们需要像这样强制多态性。

务实的故事

: type a. … 是一种结合了两个特性的简写语法:

  1. 显式多态注释 : 'a. …
    • 有助于确保定义如预期一般
    • 需要当递归完成时使用与初始调用不同的类型参数(“polymorphic recursion”即递归“非常规”ADT)
  2. 一个locally abstract type(type a) …
    • 需要当不同的分支有不同的类型时(即当“generalized” ADTs上进行模式匹配时)
    • 允许您从定义中引用类型 a,通常是在构建第一个 class 模块时(关于这个我不会多说)

这里我们使用组合语法,因为我们对 reduce 的定义以粗体显示在两种情况下。

  1. 我们有多态递归,因为 Cons(b, c) fun_chain 构建了 (a, c) fun_chain:第一个类型参数不同(我们说 fun_chain 是“非常规”ADT)。

  2. 我们有不同类型的分支,因为 Nil 构建了一个 (a, a) fun_chainCons 构建了一个 (a, c) fun_chain (我们说 fun_chain是一种“广义”ADT,简称GADT)。

明确一点:: 'a. …: type a. … 为定义生成相同的签名。 选择一种语法或另一种语法只会影响它的主体是如何进行类型检查的。对于大多数意图和目的,您可以忘记 : 'a. … 而只记住组合形式 : type a. … (因此我的故事很短)。 las,后者并没有完全包含前者,在极少数情况下,写 : type a. … 不起作用,您需要 : 'a. … (请参阅@octachron 的回答),但希望您不会绊倒经常在他们身上。

说来话长

显式多态性

OCaml 类型注释有一个肮脏的小秘密:写 let f : 'a -> 'a = … 不会 强制 f'a 中是多态的。编译器将提供的注解与推断类型统一起来,并在这样做时可以自由实例化类型变量 'a,从而导致生成的类型比预期的更不通用。例如 let f : 'a -> 'a = fun x -> x+1 是一个可接受的程序并导致 val f : int -> int。为了确保函数确实是多态的(即如果定义不够通用,编译器会拒绝定义),您必须使用以下语法使多态显式:

let f : 'a. 'a -> 'a = …

对于非递归定义,这只是人类程序员添加一个约束,使更多的程序被拒绝。

然而,在递归定义的情况下,这还有另一个含义。在对主体进行类型检查时,编译器会将提供的类型与所定义函数的所有出现的类型统一起来。未标记为多态的类型变量将在所有递归调用中相等。但是多态递归恰恰是我们使用不同类型的参数进行递归;如果没有明确的多态性,那要么会失败,要么会推断出比预期更不通用的类型。为了让它工作,我们明确标记哪些类型变量应该是多态的。

请注意,OCaml 无法自行对多态递归进行类型检查是有充分理由的:不确定性即将到来 (see Wikipedia for references)。

举个例子,让我们在这个错误的定义上做类型检查器的工作,其中多态性没有明确表示:

(* does not typecheck! *)
let rec reduce : ('a, 'c) fun_chain -> 'a -> 'c =
  fun chain x ->
    begin match chain with
    | Nil              -> x
    | Cons (f, chain') -> reduce chain' (f x)
    end

对于某些类型变量,我们从 reduce : ('a, 'c) fun_chain -> 'a -> 'cchain : ('a, 'c) fun_chain 开始 'a'c

  • 在第一个分支中,chain = Nil,所以我们了解到实际上是chain : ('c, 'c) fun_chain'a == 'c。 (不过现在这并不重要。)

  • 在第二个分支中,chain = Cons (f, chain') 所以存在一个 任意 类型 b 使得 f : 'a -> bchain' : (b, 'c) fun_chain。然后我们必须对递归调用进行类型检查 reduce chain',因此预期的参数类型 ('a, 'c) fun_chain 必须与 提供的参数类型 (b, 'c) fun_chain 统一;但没有任何信息告诉我们 b =?= 'a。所以我们拒绝这个定义,最好有一个神秘的错误信息:

Error: This expression has type ($Cons_'b, 'c) fun_chain
       but an expression was expected of type ('c, 'c) fun_chain
       The type constructor $Cons_'b would escape its scope

如果现在我们明确多态性:

(* still does not typecheck! *)
let rec reduce : 'a 'c. ('a, 'c) fun_chain -> 'a -> 'c =
  …

然后对递归调用进行类型检查不再是问题,因为我们现在知道 reduce 是具有两个“类型参数”(非标准术语)的多态,并且这些类型参数在每个reduce 的出现;递归调用使用 b'c 即使封闭调用使用 'a'c.

本地抽象类型

但是我们有第二个问题:构造函数Nil的另一个分支已经使'a'c统一了。因此,我们最终推断出一个比注释要求的更不通用的类型,并且我们报告了一个错误:

Error: This definition has type 'c. ('c, 'c) fun_chain -> 'c -> 'c
       which is less general than 'a 'c. ('a, 'c) fun_chain -> 'a -> 'c

解决办法是将类型变量变成局部抽象类型,不能统一(但我们仍然可以有关于它们的类型方程)。这样,类型方程在每个分支的本地导出,并且它们不会在 match with 构造之外发生。

'a . ...type a. ... 之间犹豫时的实际答案是始终使用后一种形式:

  • type a. ... 适用于:
    • 多态递归
    • GADT
    • 尽早提出类型错误

鉴于:

  • 'a. ... 适用于
    • 多态递归
    • 行类型变量的多态量化

因此 type a. ... 通常是 'a . ... 的严格高级版本。

除了最后一个怪点。为了详尽无遗,让我举一个对行类型变量进行量化的例子:

let f: 'a. ([> `X ] as 'a) -> unit = function
  | `X -> ()
  | _ -> ()

这里通用量化让我们可以精确控制行变量类型。例如,

let f: 'a. ([> `X ] as 'a) -> unit = function
  | `X | `Y -> ()
  | _ -> ()

产生以下错误

Error: This pattern matches values of type [? `Y ]
      but a pattern was expected which matches values of type [> `X ]
      The second variant type is bound to the universal type variable 'a,
      it may not allow the tag(s) `Y

此用例不受形式支持 type a. ... 主要是因为局部抽象类型、GADT 类型细化和类型约束的交互尚未形式化。因此,不支持第二个奇异的用例。

TL;DR;在你的问题中,只有最后两种形式是多态类型annotations。这两种形式中的后者,除了将类型注释为多态外,还引入了局部抽象类型1。这是唯一的区别。

更长的故事

现在让我们谈谈术语。以下不是类型注解(或者更恰当地说,不包含任何类型注解),

let f :         'a -> 'a = …

它被称为类型约束。类型约束要求定义值的类型与指定的类型模式兼容

在这个定义中,

let f : 'a.     'a -> 'a = …

我们有一个类型约束,其中包括 类型注释。 OCaml 用语中的短语“类型注释”意味着:用一些信息注释一个类型,即,将一些属性或 属性 附加到一个类型。在这种情况下,我们将类型 'a 注释为多态。我们没有将值 f 注释为多态的,我们也没有将值 f 注释为类型 'a -> 'a'a. 'a -> 'a。我们正在约束 f 的值与类型 'a -> 'a 兼容,并将 'a 注释为多态类型变量。

长期以来,语法 'a. 是将类型注释为多态的唯一方法,但后来 OCaml 引入了本地抽象类型。它们具有以下语法,您也可以将其添加到 collection.

let f (type t) : t -> t = ...

这会创建一个新的抽象类型构造函数,您可以在定义的范围内使用它。它没有将 t 注释为多态,因此如果您希望将其显式注释为多态,您可以编写

let f : 'a. 'a -> 'a = fun (type t) (x : t) : t -> ...

其中包括 'a 作为多态的显式类型注释和局部抽象类型的引入。不用说,编写这样的结构很麻烦,所以稍后(OCaml 4.00)他们为此引入了语法糖,这样上面的表达式就可以简单地写成,

let f : type t. t -> t = ...

因此,此语法只是两个相当正交的特征的合并:局部抽象类型和显式多态类型。

然而,这并不是合并的结果比它的部分更强大。它更像是一个十字路口。虽然生成的类型既是局部抽象的又是多态的,但它被限制为基础类型。换句话说,它约束了类型的种类,但这是higher-kinded多态性的完全不同的问题。

总而言之,尽管语法相似,但以下不是类型注释,

val f : 'a -> 'a

它被称为值规范,它是签名的一部分,表示值f 的类型为 'a -> 'a.


1)) 本地抽象类型有两个主要用例。首先,您可以在表达式中不允许使用类型变量的地方使用它们,例如,在模块和异常定义中。其次,局部抽象类型的范围超出了函数的范围,您可以通过将表达式的局部类型与抽象类型统一起来来扩展它们的范围。基本思想是表达式不能比它的类型长寿,因为在 OCaml 中类型可以在运行时创建,我们也必须小心类型的范围。通过函数参数将本地创建的类型与本地抽象类型统一起来,保证了该类型将与代替函数应用程序的某些现有类型统一。直观上,这就像传递一个类型的引用,以便可以从函数返回该类型。