polymorphism - 有人可以解释这个 OCaml 程序中使用的类型语法吗？

Question

以下类型取自this question

(* contains an error, later fixed by the OP *)
type _ task =
| Success : 'a -> 'a task
| Fail : 'a -> 'a task
| Binding : (('a task -> unit) -> unit) -> 'a task
| AndThen : ('a -> 'b task) * 'a task -> 'b task
| OnError : ('a -> 'b task) * 'a task -> 'b task

type _ stack =
| NoStack : 'a stack
| AndThenStack : ('a -> 'b task) * 'b stack -> 'a stack
| OnErrorStack : ('a -> 'b task) * 'b stack -> 'a stack

type 'a process = 
{ root: 'a task 
; stack: 'a stack 
}

我对 OCaml 比较陌生，但我从未见过 :之前使用的语法。例如，我见过这样定义的多态类型，使用 of句法

type 'a expr =
    | Base  of 'a
    | Const of bool
    | And   of 'a expr list
    | Or    of 'a expr list
    | Not   of 'a expr

在最初的问题中，我不清楚这些变体是如何构建的，因为看起来每个变体都不接受一个论点。拿这个简化的例子

type 'a stack =
  | Foo : int stack
  | Bar : string stack
;;
type 'a stack = Foo : int stack | Bar : string stack

尝试制作 int stack使用 Foo

Foo 5;;
Error: The constructor Foo expects 0 argument(s),
       but is applied here to 1 argument(s)

然而，没有争论

Foo;;
- : int stack = Foo

好的，但是 int 在哪里？ ?如何以这种类型存储数据？

在下面的 OP 程序中，他/她匹配“正常”类型，例如 Success value -> ...或 Fail value -> ... .同样，如果变体构造函数不接受参数，这个值是如何构造的？

let rec loop : 'a. 'a process -> unit = fun proc ->
match proc.root with
| Success value -> 
    let rec step = function
    | NoStack -> ()
    | AndThenStack (callback, rest) -> loop {proc with root = callback value; stack = rest }
    | OnErrorStack (_callback, rest) -> step rest  <-- ERROR HERE
    in
    step proc.stack
| Fail value -> 
    let rec step = function
    | NoStack -> ()
    | AndThenStack (_callback, rest) -> step rest
    | OnErrorStack (callback, rest) -> loop {proc with root = callback value; stack = rest }
    in
    step proc.stack
| Binding callback -> callback (fun task -> loop {proc with root = task} )
| AndThen (callback, task) -> loop {root = task; stack = AndThenStack (callback, proc.stack)}
| OnError (callback, task) -> loop {root = task; stack = OnErrorStack (callback, proc.stack)}

有人可以帮助我填补我的知识空白吗？

Answer 1

这些类型是广义代数数据类型。也称为 GADTs . GADT 使优化构造函数和类型之间的关系成为可能。

在您的示例中，GADT 用作引入存在量化类型的一种方式:删除不相关的构造函数，可以编写

type 'a task =
| Done of 'a
| AndThen : ('a -> 'b task) * 'a task -> 'b task

在这里， AndThen是一个带有两个参数的构造函数:一个回调类型 'a -> 'b task和一个 'a task并返回类型为 'b task 的任务.这个定义的一个显着特点是类型变量 'a只出现在构造函数的参数中。一个自然的问题是如果我有一个值 AndThen(f,t): 'a task ， f的类型是什么？ ?

而答案是 f的类型部分未知，我只知道有一个类型 ty使得两者 f: ty -> 'a task和 t: ty .但此时所有信息都超出了 ty的单纯存在范围。已经丢失。因此，类型 ty被称为存在量化类型。

但在这里，这个小信息仍然足以有意义地操纵这样的值(value)。我可以定义一个功能步骤

let rec step: type a. a task -> a task = function
| Done _ as x -> x
| AndThen(f,Done x) -> f x
| AndThen(f, t) -> AndThen(f, step t)

尝试应用函数 f在构造函数中 AndThen如果可能的话，
使用信息比构造函数 AndThen始终存储兼容的回调和任务对。

例如

let x: int task = Done 0
let f: int -> float task =  fun x -> Done (float_of_int (x + 1))
let y: float task = AndThen(f,x)
;; step y = Done 1.