OCaml 方差 (+'a, -'a) 和不变性

Question

写完这段代码后

module type TS = sig
  type +'a t
end
  
module T : TS = struct
  type 'a t = {info : 'a list}
end

我意识到我需要 info 可变。

我写了，然后:

module type TS = sig
  type +'a t
end
  
module T : TS = struct
  type 'a t = {mutable info : 'a list}
end

但是，惊喜，

Type declarations do not match:
  type 'a t = { mutable info : 'a list; }
is not included in
  type +'a t
Their variances do not agree.

哦，我记得听说过方差。这是关于 协方差 和 协方差 的事情。我是一个勇敢的人，我会自己找问题！

我找到了这两篇有趣的文章（here and here），我明白了！

我会写

module type TS = sig
  type (-'a, +'b) t
end
  
module T : TS = struct
  type ('a, 'b) t = 'a -> 'b
end

但后来我想知道。为什么 mutable 数据类型是不变的而不仅仅是协变的？

我的意思是，我知道 'A list 可以被视为 ('A | 'B) list 的子类型，因为我的列表无法更改。对于函数也是一样，如果我有一个 'A | 'B -> 'C 类型的函数，它可以被认为是 'A -> 'C | 'D 类型函数的子类型，因为如果我的函数可以处理 'A 和 'B's 它只能处理 'A's 如果我只处理 return 'C's 我肯定可以期待 'C 或 'D's (但我只会得到 'C's).

但是对于数组？如果我有一个 'A array，我不能将它视为一个 ('A | 'B) array，因为如果我修改数组中的一个元素并放置一个 'B，那么我的数组类型是错误的，因为它确实是一个('A | 'B) array 而不是 'A array 了。但是 ('A | 'B) array 作为 'A array 呢？是的，这会很奇怪，因为我的数组可以包含 'B 但奇怪的是我认为它与函数相同。也许，最后，我并没有完全理解，但我想把我的想法放在这里，因为我花了很长时间才理解它。

TL;DR :

persistent : +'a

functions : -'a

mutable : invariant ('a) ? Why can't I force it to be -'a ?

Answer 1

我认为最简单的解释是可变值有两个内在操作：getter 和 setter，它们使用字段访问和字段集语法表示：

type 'a t = {mutable data : 'a}

let x = {data = 42}

(* getter *)
x.data

(* setter *)
x.data <- 56

Getter 具有类型 'a t -> 'a，其中 'a 类型变量出现在右侧（因此它施加了协方差约束），并且 setter具有类型 'a t -> 'a -> unit ，其中类型变量出现在箭头的左侧，这会施加逆变约束。所以，我们有一个既是协变又是逆变的类型，这意味着类型变量 'a 是不变的。

Answer 2

您的类型 t 基本上允许两种操作：获取和设置。非正式地，getting 的类型为 'a t -> 'a list，setting 的类型为 'a t -> 'a list -> unit。结合起来，'a 既出现在正位也出现在负位。

[编辑：以下是我最初写的内容的（希望）更清晰的版本。我认为它更优越，所以我删除了以前的版本。]

我会尽量让它更明确。假设 sub 是 super 的真子类型，而 witness 是类型 super 的某个值，它不是类型 sub 的值。现在让 f : sub -> unit 成为某个在值 witness 上失败的函数。类型安全是为了确保 witness 永远不会传递给 f。我将通过示例说明，如果允许将 sub t 视为 super t 的子类型，或者相反。

let v_super = ({ info = [witness]; } : super t) in
let v_sub = ( v_super : sub t ) in   (* Suppose this was allowed. *)
List.map f v_sub.info   (* Equivalent to f witness. Woops. *)

因此不允许将 super t 视为 sub t 的子类型。这显示了您已经知道的协方差。现在是逆变。

let v_sub = ({ info = []; } : sub t) in
let v_super = ( v_sub : super t ) in  (* Suppose this was allowed. *)
v_super.info <- [witness];
   (* As v_sub and v_super are the same thing,
      we have v_sub.info=[witness] once more. *)
List.map f v_sub.info   (* Woops again. *)

因此，也不允许将 sub t 视为 super t 的子类型，这表明逆变。在一起，'a t 是不变的。

OCaml 方差 (+'a, -'a) 和不变性

OCaml variance (+'a, -'a) and invariance

ocaml

covariance

contravariance

invariance