当前位置：文江博客话题详情

`＆＃x27; A.和`type A type a。

发布于 2025-01-25 06:25:23 字数 320 浏览 1 评论 0 原文

OCAML具有几种不同的多态性注释语法：

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

我们经常在使用精美的代数数据类型（通常是GADTS）时看到它们，似乎是必要的。

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

原文

OCaml has several different syntaxes for a polymorphic type annotation :

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

We often see them when using fancy algebraic datatypes (typically, GADTs), where they seem to be necessary.

What is the difference between these syntaxes? When and why each one must be used?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

青芜 2025-02-01 06:25:23

以下是替代说明，并具有不同量的细节，具体取决于您的赶时间。;-)

我将使用以下代码（从其他问题）作为运行示例。在这里，实际上需要对 REDAL 定义的类型注释才能使其成为Typecheck。

(* 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

简短故事

关于畅通无阻的，诸如 ：＆nbsp;'a＆nbsp;＆gt;＆nbsp;'a dos 不是 doce force proloce prolymormorist ：：类型检查器可以将统一变量'a 改进到某物。这种语法确实具有误导性，因为在模块签名中，对阀门启动IE的注释相同 执行多态性。

：type a。 …是一种具有显式（强制）多态性的类型注释 。您可以将其视为通用量词（对于所有 a “）。例如，

let some : type a. a -> a option =
  fun x -> Some x

意味着“全部”类型 a ，您可以将 a 给予，然后它将返回 a＆nbsp ;选项。

此答案开始时的代码利用了类型系统的高级功能，即多态性递归和具有不同类型的分支，并且在一个损失中留下类型推理。为了在这种情况下进行类型的程序，我们需要强制这样的多态性。请注意，在此语法中， a 是类型 name （无引用），而不是类型统一变量。

：'a。 …是另一种迫使多态性的语法，但实际上是由：＆nbsp; type＆nbsp; a。＆nbsp;…所包含的。

务实的故事

：type a。 …是一种结合了两个功能的短手语法：

AN 显式多态性注释 ：'a。 …
- 对于确保定义与预期
- 必需使用类型参数进行递归时，与初始调用的参数不同（ “多态性递归” ie recursion在“非规范” ADT上）
a 本地抽象类型 （类型A）…

必需当不同的分支具有不同类型时（即 pattern matching on “广义” adts ）

允许您从定义内部参考类型 a ，通常是在构建头等模块时（我不会对此说更多）

允许您从定义内部参考 a ，通常在此处我们使用组合的语法，因为我们对降低的定义属于两种情况下的粗体。

我们有多态性递归，因为 cons 构建（a，＆nbsp; c）fun_chain 来自a （b，＆nbsp; c）fun_chain ：第一个类型的参数有所不同（我们说 fun_chain 是“非规范” ADT）。
我们有不同类型的分支机构，因为 nil 构建（a，＆nbsp; a）fun_chain 而 cons> cons 构建（ a＆nbsp; c）fun_chain （我们说 fun_chain 是“概括” ADT，或者是简短的GADT）。

要清楚： ：＆nbsp;' 选择一种语法或另一种语法对其身体的打字方式有影响。为了大多数目的和目的，您可能会忘记：＆nbsp;' las，后者并不能完全包含前者，在罕见的情况下，写：type＆nbsp; a。。

长篇小说的

明确多态性

OCAML类型注释有一个肮脏的小秘密：写让f＆nbsp;：'a＆nbsp; - ＆gt; 'a =…不 force f 在'a 中是多态性的。编译器将提供的注释与推断类型统一，并且可以自由实例化变量'a ，从而导致类型较小的类型。例如令f＆nbsp;：'a - ＆gt; 'a = fun x-＆gt; X+1 是一个接受的程序，可导致 val f＆nbsp;：int - ＆gt; int 。为了确保该功能确实是多态性的（即，如果编译器不够一般拒绝定义），则必须具有以下语法，使多态性明确：

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

对于非寻求性定义，这仅仅是人类程序员添加一个约束，使更多程序被拒绝。

但是，在递归定义的情况下，这有另一个含义。当打字时，编译器将与所定义函数的所有出现类型统一类型。在所有递归调用中，未标记为多态性的类型变量将相等。但是，当我们以不同的类型参数复发时，多态性递归恰恰是。如果没有明确的多态性，那将失败或推断出比预期的一般类型。为了使它起作用，我们明确标记了哪种类型变量应该是多态性的。

请注意，OCAML无法单独打字多态性递归是有充分理由的：拐角处有不确定性（）。

例如，让我们在这个错误的定义上完成Typechecker的作业，在此错误的定义中，多态性并非明确：

(* 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

我们以 redaim＆nbsp;：：{'a，＆nbsp;'c）fun_chain--＆gt; 'a - ＆gt; 'c 和链＆nbsp; ：（'a，＆nbsp;'c）fun_chain 对于某些类型变量'a 和'c 'c 。

在第一个分支中，链条＆nbsp; =＆nbsp; nil ，因此我们了解到，实际上，链条＆nbsp;：:（'c，＆nbsp;'c）代码>'a＆nbsp; ==＆nbsp;'c 。我们统一两个类型变量。（但是现在没关系。）
在第二个分支中，链= cons＆nbsp;（f，＆nbsp;链'），因此存在 nutyary 键入 b ，以便 f＆nbsp;：'a - ＆gt; b 和链'＆nbsp;：（b，＆nbsp;'c）fun_chain 。然后，我们必须输入递归调用降低链'，因此预期参数类型（'a，＆nbsp;'c）fun_chain 必须用统一提供的参数类型（b，＆nbsp;'c）fun_chain ;但是没有什么可以告诉我们 b＆nbsp; ==＆nbsp;'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 =
  …

然后打字递归调用不再是问题，因为我们现在知道 redy> redy> redaim 是具有两个“类型参数”（非标准术语）的多态性，这些类型参数在每次出现 redaim> redaim 的情况下都是独立实例化的；递归调用使用 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

解决方案是将类型变量转换为本地抽象的类型，而这些变量不能统一（但是我们仍然可以具有有关它们的类型方程）。这样，类型方程将在本地派生到每个分支，并且它们不会与构造匹配之外。

Below are alternative explanations with a varying amount of detail, depending on how much of a hurry you’re in. ;-)

I will use the following code (drawn from that other question) as a running example. Here, the type annotation on the definition of reduce is actually required to make it typecheck.

(* 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

The short story

On let-definitions, an annotation like : 'a -> 'a does not force polymorphism: the type-checker may refine the unification variable 'a to something. This bit of syntax is misleading indeed, because the same annotation on a val-declaration i.e. in a module signature does enforce polymorphism.

: type a. … is a type annotation with explicit (forced) polymorphism. You can think of this as the universal quantifier (∀ a, “for all a“). For instance,

let some : type a. a -> a option =
  fun x -> Some x

means that “for all” type a, you can give an a to some and then it will return an a option.

The code at the beginning of this answer makes use of advanced features of the type system, namely, polymorphic recursion and branches with different types, and that leaves type inference at a loss. In order to have a program typecheck in such a situation, we need to force polymorphism like this. Beware that in this syntax, a is a type name (no leading quote) rather than a type unification variable.

: 'a. … is another syntax that forces polymorphism, but it is practically subsumed by : type a. … so you will hardly need it at all.

The pragmatic story

: type a. … is a short-hand syntax that combines two features:

an explicitly polymorphic annotation : 'a. …
- useful for ensuring a definition is as general as intended
- required when recursion is done with type parameters different from those of the initial call (“polymorphic recursion” i.e. recursion on “non-regular” ADTs)
a locally abstract type (type a) …
- required when different branches have different types (i.e. when pattern-matching on “generalized” ADTs)
- allows you to refer to type a from inside the definition, typically when building a first-class module (I won’t say more about this)

Here we use the combined syntax because our definition of reduce falls under both situations in bold.

We have polymorphic recursion because Cons builds a (a, c) fun_chain from a (b, c) fun_chain: the first type parameter differs (we say that fun_chain is a “non-regular” ADT).
We have branches with different types because Nil builds a (a, a) fun_chain whereas Cons builds a (a, c) fun_chain (we say that fun_chain is a “generalized” ADT, or GADT for short).

Just to be clear: : 'a. … and : type a. … produce the same signature for the definition. Choosing one syntax or the other only has an influence on how its body is typechecked. For most intents and purposes, you can forget about : 'a. … and just remember the combined form : type a. …. Alas, the latter does not completely subsume the former, there are rare situations where writing : type a. … wouldn’t work and you would need : 'a. … (see @octachron’s answer) but, hopefully, you won’t stumble upon them often.

The long story

Explicit polymorphism

OCaml type annotations have a dirty little secret: writing let f : 'a -> 'a = … doesn’t force f to be polymorphic in 'a. The compiler unifies the provided annotation with the inferred type and is free to instantiate the type variable 'a while doing so, leading to a less general type than intended. For instance let f : 'a -> 'a = fun x -> x+1 is an accepted program and leads to val f : int -> int. To ensure the function is indeed polymorphic (i.e. to have the compiler reject the definition if it is not general enough), you have to make the polymorphism explicit, with the following syntax:

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

For a non-recursive definition, this is merely the human programmer adding a constraint which makes more programs be rejected.

In the case of a recursive definition however, this has another implication. When typechecking the body, the compiler will unify the provided type with the types of all occurrences of the function being defined. Type variables which are not marked as polymorphic will be made equal in all recursive calls. But polymorphic recursion is precisely when we recurse with differing type parameters; without explicit polymorphism, that would either fail or infer a less general type than intended. To make it work, we explicitly mark which type variables should be polymorphic.

Note that there is a good reason why OCaml cannot typecheck polymorphic recursion on its own: there is undecidability around the corner (see Wikipedia for references).

As an example, let’s do the job of the typechecker on this faulty definition, where polymorphism is not made explicit:

(* 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

We start with reduce : ('a, 'c) fun_chain -> 'a -> 'c and chain : ('a, 'c) fun_chain for some type variables 'a and 'c.

In the first branch, chain = Nil, so we learn that in fact chain : ('c, 'c) fun_chain and 'a == 'c. We unify both type variables. (That doesn’t matter right now, though.)
In the second branch, chain = Cons (f, chain') so there exists an arbitrary type b such that f : 'a -> b and chain' : (b, 'c) fun_chain. Then we must typecheck the recursive call reduce chain', so the expected argument type ('a, 'c) fun_chain must unify with the provided argument type (b, 'c) fun_chain; but nothing tells us that b == 'a. So we reject this definition, preferably (as is tradition) with a cryptic error message:

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

If now we make polymorphism explicit:

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

Then typechecking the recursive call is not a problem anymore, because we now know that reduce is polymorphic with two “type parameters” (non-standard terminology), and these type parameters are instantiated independently at each occurrence of reduce; the recursive call uses b and 'c even though the enclosing call uses 'a and 'c.

Locally abstract types

But we have a second problem: the other branch, for constructor Nil, has made 'a be unified with 'c. Hence we end up inferring a less general type than what the annotation mandated, and we report an error:

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

The solution is to turn the type variables into locally abstract types, which cannot be unified (but we can still have type equations about them). That way, type equations are derived locally to each branch and they do not transpire outside of the match with construct.

回复收藏 0 原文

坚持沉默 2025-02-01 06:25:23

'a之间犹豫时的实际答案。 ... 和类型A。 ... 始终使用后一种形式：

类型A。 ... 与：
- 多态性递归
- gadts
- 提早提高类型错误

，而

'a。 ... 使用
- 多态性递归
- 对行类型变量的多态性定量

多态性定量，因此类型a。 ... 通常是'a的严格优越版本。 ... 。

除了最后一个奇怪的观点。为了详尽，让我给出一个对行类型变量的量化示例：

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

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

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

产生以下错误

 错误：此模式与类型的值匹配[？ `y]
      但是，预期的模式与[＆gt类型的值匹配； `x]
      第二个变体类型与通用类型变量'a，
      它可能不允许标签

此用例不受类型A的支持。 ... 主要是因为本地抽象类型的相互作用，GADTS类型的改进和类型约束尚未被形式化。因此，不支持第二种外来用例。

The practical answer when hesitating between 'a . ... and type a. ... is to always use the latter form:

type a. ... works with:
- polymorphic recursion
- GADTs
- raise type errors early

whereas:

'a. ... works with
- polymorphic recursion
- polymorphic quantification over row type variables

Thus type a. ... is generally a strictly superior version of 'a . ... .

Except for the last strange point. For the sake exhaustiveness, let me give an example of quantification over a row type variable:

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

Here the universal quantification allows us to control precisely the row variable type. For instance,

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

yields the following error

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

This use case is not supported by the form type a. ... mostly because the interaction of locally abstract type, GADTs type refinement and type constraints has not been formalized. Thus this second exotic use case is not supported.

回复收藏 0 原文

自我难过 2025-02-01 06:25:23

tl; dr;在您的问题中，只有最后两种形式是多态类型注释。这两种形式的后者除了注释类型的多态性外，还引入了本地抽象的类型¹。这是唯一的区别。

现在较长的故事

让我们谈谈术语。以下不是类型的注释（或更正确地不包含任何类型的注释），

let f :         'a -> 'a = …

而是称为a 类型约束。类型约束要求定义值的类型与指定的类型架构兼容。

在此定义中，

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

我们有一个类型约束，其中包括类型注释。 ocaml术语中的短语“类型注释”表示： 用某些信息，即，将某些属性或属性附加到类型上。在这种情况下，我们注释类型'a 作为多态性。我们没有注释值 f ，因为多态也不会用类型'a - ＆gt注释值 f ; 'a 或'a。 'a - ＆gt; 'a 。我们正在限制 f 的值，以使其与类型'a - ＆gt兼容。 'a 和注释'a 作为多态类型变量。

长期以来，语法'a。是注释类型作为多态性的唯一方法，但后来OCAML引入了本地抽象类型。他们具有以下语法，您也可以将其添加到您的集合中。

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 = ...

因此，该语法只是两个相当的融合正交特征：本地抽象类型和明确的多态性类型。

但是，这种合并的结果并不比其部分强。这更像是一个十字路口。虽然生成的类型既是局部抽象的，又是多态性的，但它被限制为地面类型。换句话说，它限制了类型的类型，但这是一个完全不同的多态性的问题。

得出结论，尽管语法相似，但以下不是类型的注释，

val f : 'a -> 'a

它称为a value规范，它是a signature 的一部分，它是表示值 f 具有类型'a - ＆gt; 'a 。

^1））本地抽象类型有两个主要用例。首先，您可以在不允许使用类型变量的地方（例如，在模块和异常定义）中使用它们。其次，本地抽象类型的范围超过了该函数的范围，您可以通过统一使用抽象类型的局部表达式的类型来扩展其范围。基本的想法是，表达式无法超过其类型，并且由于可以在运行时创建OCAML类型，因此我们也必须谨慎对待该类型的程度。通过函数参数将本地创建的类型统一使用本地抽象类型，可以确保此类型将与某些现有类型统一在功能应用程序的位置。直观地，这就像传递一种类型的参考，以便可以从函数返回类型。

TL;DR; In your question, only the last two forms are polymorphic type annotations. The latter of these two forms, in addition to annotating a type as polymorphic, introduces a locally abstract type¹. This is the only difference.

The longer story

Now let's speak a little bit about the terminology. The following is not a type annotation (or, more properly, doesn't contain any type annotations),

let f :         'a -> 'a = …

It is called a type constraint. A type constraint requires the type of the defined value to be compatible with the specified type schemata.

In this definition,

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

we have a type constraint that includes a type annotation. The phrase "type annotation" in OCaml parlance means: annotating a type with some information, i.e., attaching some attribute or a property to a type. In this case, we annotate type 'a as polymorphic. We're not annotating the value f as polymorphic neither are we annotating the value f with type 'a -> 'a or 'a. 'a -> 'a. We are constraining the value of f to be compatible with type 'a -> 'a and annotate 'a as a polymorphic type variable.

For a long time, syntax 'a. was the only way to annotate type as polymorphic, but later OCaml introduced locally abstract types. They have the following syntax, which you could also add to your collection.

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

Which creates a fresh abstract type constructor that you can use in the scope of the definition. It doesn't annotate t as polymorphic though, so if you want it to be explicitly annotated as polymorphic you could write,

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

which includes both an explicit type annotation of 'a as polymorphic and the introduction of a locally abstract type. Needless to say, it is cumbersome to write such constructions, so a little bit later (OCaml 4.00) they introduced syntactic sugar for that so that the above expression could be written as simple as,

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

Therefore, this syntax is just an amalgamation of two rather orthogonal features: locally abstract types and explicitly polymorphic types.

It is not however that the result of this amalgamation is stronger than its parts. It is more like an intersection. Whilst the generated type is both locally abstract and polymorphic, it is constrained to be a ground type. In other words, it constrains the kind of the type, but this is a completely different problem of higher-kinded polymorphism.

And to conclude the story, despite the syntax similarities, the following is not a type annotation,

val f : 'a -> 'a

It is called a value specification, which is a part of a signature, and it denotes that the value f has type 'a -> 'a.

¹⁾) Locally abstract types have two main use cases. First, you can use them inside your expression in places where type variables are not permitted, e.g., in modules and exceptions definitions. Second, the scope of the locally abstract type exceeds the scope of the function, which you can employ by unifying types that are local to your expression with the abstract type to extend their scopes. The underlying idea is that the expression can not outlive its type and since in OCaml types could be created in runtime we have to be careful with the extent of the type as well. Unifying a locally created type with a locally abstract type via a function parameter guarantees that this type will be unified with some existing type in the place of the function application. Intuitively, it is like passing a reference for a type, so that the type could be returned from the function.

回复收藏 0 原文

~没有更多了~

关于作者

清晰传感

暂无简介

文章

28 人气

关注发私信

友情链接

文江博客

`＆＃x27; A.和`type A type a。

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（3）

简短故事

务实的故事

长篇小说的

明确多态性

本地抽象类型

The short story

The pragmatic story

The long story

Explicit polymorphism

Locally abstract types

现在较长的故事

The longer story

关于作者

相关话题

热门标签

推荐作者

李珊平

Quxin

范无咎

github_ZOJ2N8YxBm

若言

南…巷孤猫

友情链接

`＆＃x27; A.和`type A type a。

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（3）

简短故事

务实的故事

长篇小说的

明确多态性

本地抽象类型

The short story

The pragmatic story

The long story

Explicit polymorphism

Locally abstract types

现在较长的故事

The longer story

关于作者

相关话题

热门标签

推荐作者

李珊平

Quxin

范无咎

github_ZOJ2N8YxBm

若言

南…巷孤猫

友情链接

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。