第 6 章 多态及其限制



本章涵盖了与多态函数和类型的限制相关的更高级的问题。在 OCaml 中,有些情况下,类型检查器推断出的类型可能比预期类型泛化程度低。这种非泛化性可能源于副作用与类型之间的交互,也可能源于隐式多态递归和高阶多态性的困难。

本章详细介绍了每种情况,并在可能的情况下说明如何恢复泛化性。

1 弱多态和变异

1.1 弱多态类型

可能最常见的非泛化示例来自多态类型和变异之间的交互。当对以下表达式进行类型推断时,就会出现一个简单的示例

# let store = ref None ;;
val store : '_weak1 option ref = {contents = None}

由于 None 的类型是 'a option,而函数 ref 的类型是 'b -> 'b ref,因此 store 类型的一个自然推论是 'a option ref。但是,推断出的类型 '_weak1 option ref 却有所不同。类型变量名称以 _weak 前缀开头(例如 '_weak1)的类型变量是弱多态类型变量,有时简称为“弱类型变量”。弱类型变量是当前未知的单个类型的占位符。一旦占位符类型 '_weak1 后面的特定类型 t 已知,所有 '_weak1 的出现都将被 t 替换。例如,我们可以定义另一个选项引用并在其中存储一个 int

# let another_store = ref None ;;
val another_store : '_weak2 option ref = {contents = None}
# another_store := Some 0; another_store ;;
- : int option ref = {contents = Some 0}

another_store 中存储一个 int 之后,another_store 的类型已从 '_weak2 option ref 更新为 int option ref。弱多态类型变量和通用多态类型变量之间的这种区别可以保护 OCaml 程序免受不安全性和运行时错误的影响。要了解不安全性可能来自哪里,请考虑这个简单的函数,它在存在的情况下,将值 x 与存储在 store 引用中的值交换

# let swap store x = match !store with | None -> store := Some x; x | Some y -> store := Some x; y;;
val swap : 'a option ref -> 'a -> 'a = <fun>

我们可以将此函数应用于我们的存储

# let one = swap store 1 let one_again = swap store 2 let two = swap store 3;;
val one : int = 1 val one_again : int = 1 val two : int = 2

经过这三次交换后,存储的值为 3。到目前为止一切正常。然后,我们可以尝试将 3 与一个更有趣的值交换,例如一个函数

# let error = swap store (fun x -> x);;
错误:此表达式不应该是一个函数,预期类型为 int

此时,类型检查器正确地抱怨说无法交换整数和函数,并且应该始终用另一个 int 交换 int。此外,类型检查器阻止我们手动更改 store 存储的值的类型

# store := Some (fun x -> x);;
错误:此表达式不应该是一个函数,预期类型为 int

实际上,查看 store 的类型,我们可以看到弱类型 '_weak1 已被类型 int 替换

# store;;
- : int option ref = {contents = Some 3}

因此,在 store 中放置一个 int 之后,我们不能使用它来存储除 int 之外的任何值。更一般地说,弱类型可以保护程序免受对具有多态类型的值的过度变异。

此外,弱类型不能出现在顶级模块的签名中:类型必须在编译时已知。否则,不同的编译单元可能会用不同的且不兼容的类型替换弱类型。因此,编译以下一小段代码

let option_ref = ref None

会导致编译错误

Error: The type of this expression, '_weak1 option ref,
       contains type variables that cannot be generalized

要解决此错误,只需添加显式类型注释以在声明时指定类型即可

let option_ref: int option ref = ref None

无论如何,对于此类全局可变变量,这是一种良好的实践。否则,它们将选择第一次使用的类型。如果此时存在错误,则在稍后,正确的用法被标记为错误时,可能会导致令人困惑的类型错误。

1.2 值限制

以模块化方式识别应将多态类型替换为弱类型的确切上下文是一个难题。实际上,类型系统必须处理函数可能隐藏持久可变状态的可能性。例如,以下函数使用内部引用来实现一个延迟的恒等函数

# let make_fake_id () = let store = ref None in fun x -> swap store x ;;
val make_fake_id : unit -> 'a -> 'a = <fun>
# let fake_id = make_fake_id();;
val fake_id : '_weak3 -> '_weak3 = <fun>

将此 fake_id 函数应用于不同类型的值是不安全的。因此,函数 fake_id 正确地被分配了类型 '_weak3 -> '_weak3 而不是 'a -> 'a。同时,应该能够使用局部可变状态而不影响函数的类型。

为了规避这些双重困难,类型检查器认为函数返回的任何值都可能依赖于幕后的持久可变状态,并且应该被赋予弱类型。对可变值和函数应用结果的类型的这种限制称为值限制。请注意,此值限制是保守的:在某些情况下,值限制过于谨慎,会为可以安全地泛化为多态类型的值赋予弱类型

# let not_id = (fun x -> x) (fun x -> x);;
val not_id : '_weak4 -> '_weak4 = <fun>

这种情况在使用高阶函数定义函数时经常发生。为了避免此问题,一种解决方案是向函数添加一个显式参数

# let id_again = fun x -> (fun x -> x) (fun x -> x) x;;
val id_again : 'a -> 'a = <fun>

使用此参数,id_again 被类型检查器视为函数定义,因此可以对其进行泛化。这种操作在 lambda 演算中称为 eta 展开,有时也以此名称称呼。

1.3 放宽的值限制

针对不必要弱类型的另一个部分解决方案是直接在类型检查器中实现的。简而言之,可以证明,仅作为协变位置(也称为正位置)中的类型参数出现的弱类型可以安全地泛化为多态类型。例如,类型 'a list'a 中是协变的

# let f () = [];;
val f : unit -> 'a list = <fun>
# let empty = f ();;
val empty : 'a list = []

请注意,推断出的 empty 类型是 'a list,而不是根据值限制应该出现的 '_weak5 list

值限制与协变类型参数的这种泛化相结合,称为放宽的值限制。

1.4 方差和值限制

方差描述了类型构造函数相对于子类型化的行为。例如,考虑一对类型 xxy,其中 xxy 的子类型,表示为 x :> xy

# type x = [ `X ];;
type x = [ `X ]
# type xy = [ `X | `Y ];;
type xy = [ `X | `Y ]

由于 xxy 的子类型,因此我们可以将类型 x 的值转换为类型 xy 的值

# let x:x = `X;;
val x : x = `X
# let x' = ( x :> xy);;
val x' : xy = `X

类似地,如果我们有一个类型为 x list 的值,我们可以将其转换为类型为 xy list 的值,因为我们可以逐个转换每个元素

# let l:x list = [`X; `X];;
val l : x list = [`X; `X]
# let l' = ( l :> xy list);;
val l' : xy list = [`X; `X]

换句话说,x :> xy 意味着 x list :> xy list,因此类型构造函数 'a list 在其参数 'a 中是协变的(它保留了子类型化)。

相反,如果我们有一个可以处理类型为 xy 的值的函数

# let f: xy -> unit = function | `X -> () | `Y -> ();;
val f : xy -> unit = <fun>

它也可以处理类型为 x 的值

# let f' = (f :> x -> unit);;
val f' : x -> unit = <fun>

请注意,我们可以将 ff' 的类型重写为

# type 'a proc = 'a -> unit let f' = (f: xy proc :> x proc);;
type 'a proc = 'a -> unit val f' : x proc = <fun>

在这种情况下,我们有 x :> xy 意味着 xy proc :> x proc。请注意,第二个子类型关系反转了 xxy 的顺序:类型构造函数 'a proc 在其参数 'a 中是逆变的。更一般地,函数类型构造函数 'a -> 'b 在其返回类型 'b 中是协变的,在其参数类型 'a 中是逆变的。

类型构造函数在其某些类型参数中也可以是不变的,既不是协变也不是逆变。一个典型的例子是引用

# let x: x ref = ref `X;;
val x : x ref = {contents = `X}

如果我们能够将 x 作为变量 xy 转换为类型 xy ref,我们就可以使用 xy 在引用中存储值 `Y,然后使用 x 值将此内容读取为类型 x 的值,这将破坏类型系统。

更一般地,只要类型变量出现在描述可变状态的位置,它就成为不变的。作为推论,协变变量永远不会表示可变位置,并且可以安全地泛化。对于更好的描述,感兴趣的读者可以查阅 Jacques Garrigue 关于 http://www.math.nagoya-u.ac.jp/~garrigue/papers/morepoly-long.pdf 的原始文章。

放宽的值限制和类型参数协变性共同帮助避免了许多情况下的 eta 展开。

1.5 抽象数据类型

此外,当类型定义公开时,类型检查器能够自行推断方差信息,并且即使无意中也可以从放宽的值限制中获益。但是,在定义新的抽象类型时,情况不再如此。作为说明,我们可以将模块类型集合定义为

# module type COLLECTION = sig type 'a t val empty: unit -> 'a t end module Implementation = struct type 'a t = 'a list let empty ()= [] end;;
module type COLLECTION = sig type 'a t val empty : unit -> 'a t end module Implementation : sig type 'a t = 'a list val empty : unit -> 'a list end
# module List2: COLLECTION = Implementation;;
module List2 : COLLECTION

在这种情况下,当将模块 List2 转换为模块类型 COLLECTION 时,类型检查器会忘记 'a List2.t'a 中是协变的。因此,放宽的值限制不再适用

# List2.empty ();;
- : '_weak5 List2.t = <abstr>

为了保持放宽的值限制,我们需要将抽象类型 'a COLLECTION.t 声明为在 'a 中是协变的

# module type COLLECTION = sig type +'a t val empty: unit -> 'a t end module List2: COLLECTION = Implementation;;
module type COLLECTION = sig type +'a t val empty : unit -> 'a t end module List2 : COLLECTION

然后我们恢复多态性

# List2.empty ();;
- : 'a List2.t = <abstr>

2 多态递归

第二大类非泛型直接与多态函数的类型推断问题相关。在某些情况下,OCaml 推断的类型可能不够通用,无法允许定义某些递归函数,特别是对于作用于非正则代数数据类型的递归函数。

对于正则多态代数数据类型,类型构造函数的类型参数在类型定义中是常数。例如,我们可以查看定义为以下形式的任意嵌套列表:

# type 'a regular_nested = List of 'a list | Nested of 'a regular_nested list let l = Nested[ List [1]; Nested [List[2;3]]; Nested[Nested[]] ];;
type 'a regular_nested = List of 'a list | Nested of 'a regular_nested list val l : int regular_nested = Nested [List [1]; Nested [List [2; 3]]; Nested [Nested []]]

请注意,类型构造函数 regular_nested 在上面的定义中始终显示为 'a regular_nested,使用相同的参数 'a。使用此类型,我们可以使用经典的递归函数计算最大深度

# let rec maximal_depth = function | List _ -> 1 | Nested [] -> 0 | Nested (a::q) -> 1 + max (maximal_depth a) (maximal_depth (Nested q));;
val maximal_depth : 'a regular_nested -> int = <fun>

非正则递归代数数据类型对应于其参数类型在类型定义的左侧和右侧之间变化的多态代数数据类型。例如,定义一个数据类型来确保所有列表都嵌套在相同的深度可能很有趣

# type 'a nested = List of 'a list | Nested of 'a list nested;;
type 'a nested = List of 'a list | Nested of 'a list nested

直观地,类型为'a nested的值是一个列表的列表……列表的元素a,嵌套了k层列表。然后,我们可以将定义在regular_depth上的maximal_depth函数改编成一个计算此kdepth函数。作为第一次尝试,我们可以定义

# let rec depth = function | List _ -> 1 | Nested n -> 1 + depth n;;
错误:此表达式的类型为 'a list nested,但期望表达式的类型为 'a nested 类型变量 'a 出现在 'a list 内部

此处的类型错误源于以下事实:在定义depth期间,类型检查器首先将depth的类型赋值为'a -> 'b 。在键入模式匹配时,'a -> 'b变为'a nested -> 'b,然后在键入List分支后变为'a nested -> int。但是,在键入Nested分支中的应用程序depth n时,类型检查器遇到一个问题:depth n应用于'a list nested,因此它必须具有类型'a list nested -> 'b。将此约束与先前的约束统一会导致不可能的约束'a list nested = 'a nested。换句话说,在其定义中,递归函数depth应用于类型为'a t的值,由于类型构造器nested的非正则性,这些值具有不同的类型'a。这会产生问题,因为类型检查器仅在函数depth定义处引入了新的类型变量'a,而在这里,我们需要为函数depth的每个应用使用不同的类型变量。

2.1 显式多态注释

解决此难题的方案是对类型'a使用显式多态类型注释

# let rec depth: 'a. 'a nested -> int = function | List _ -> 1 | Nested n -> 1 + depth n;;
val depth : 'a nested -> int = <fun>
# depth ( Nested(List [ [7]; [8] ]) );;
- : int = 2

depth的类型'a.'a nested -> int中,类型变量'a被普遍量化。换句话说,'a.'a nested -> int读作“对于所有类型'adepth'a nested值映射到整数”。而标准类型'a nested -> int可以解释为“设一个类型变量'a,然后depth'a nested值映射到整数”。这两个类型表达式有两个主要区别。首先,显式多态注释指示类型检查器在每次应用函数depth时都需要引入一个新的类型变量。这解决了我们在函数depth定义中遇到的问题。

其次,它还通知类型检查器函数的类型应该是多态的。实际上,如果没有显式多态类型注释,则以下类型注释是完全有效的

# let sum: 'a -> 'b -> 'c = fun x y -> x + y;;
val sum : int -> int -> int = <fun>

因为'a'b'c表示可能或可能不是多态的类型变量。而将显式多态类型与非多态类型统一是错误的

# let sum: 'a 'b 'c. 'a -> 'b -> 'c = fun x y -> x + y;;
错误:此定义的类型为 int -> int -> int,这比 'a 'b 'c. 'a -> 'b -> 'c 不那么通用

这里需要注意的是,不需要完全显式地指定depth的类型:只需为普遍量化的类型变量添加注释即可

# let rec depth: 'a. 'a nested -> _ = function | List _ -> 1 | Nested n -> 1 + depth n;;
val depth : 'a nested -> int = <fun>
# depth ( Nested(List [ [7]; [8] ]) );;
- : int = 2

2.2 更多示例

使用显式多态注释,可以实现任何仅依赖于嵌套列表结构而不依赖于元素类型的递归函数。例如,一个更复杂的示例是计算嵌套列表中元素的总数

# let len nested = let map_and_sum f = List.fold_left (fun acc x -> acc + f x) 0 in let rec len: 'a. ('a list -> int ) -> 'a nested -> int = fun nested_len n -> match n with | List l -> nested_len l | Nested n -> len (map_and_sum nested_len) n in len List.length nested;;
val len : 'a nested -> int = <fun>
# len (Nested(Nested(List [ [ [1;2]; [3] ]; [ []; [4]; [5;6;7]]; [[]] ])));;
- : int = 7

类似地,可能需要使用多个显式多态类型变量,例如计算嵌套列表的嵌套列表长度

# let shape n = let rec shape: 'a 'b. ('a nested -> int nested) -> ('b list list -> 'a list) -> 'b nested -> int nested = fun nest nested_shape -> function | List l -> raise (Invalid_argument "shape requires nested_list of depth greater than 1") | Nested (List l) -> nest @@ List (nested_shape l) | Nested n -> let nested_shape = List.map nested_shape in let nest x = nest (Nested x) in shape nest nested_shape n in shape (fun n -> n ) (fun l -> List.map List.length l ) n;;
val shape : 'a nested -> int nested = <fun>
# shape (Nested(Nested(List [ [ [1;2]; [3] ]; [ []; [4]; [5;6;7]]; [[]] ])));;
- : int nested = Nested (List [[2; 1]; [0; 1; 3]; [0]])

3 高阶多态函数

然而,显式多态注释不足以涵盖所有函数的推断类型不如预期通用情况。当使用多态函数作为高阶函数的参数时,会出现类似的问题。例如,我们可能希望计算两个嵌套列表的平均深度或长度

# let average_depth x y = (depth x + depth y) / 2;;
val average_depth : 'a nested -> 'b nested -> int = <fun>
# let average_len x y = (len x + len y) / 2;;
val average_len : 'a nested -> 'b nested -> int = <fun>
# let one = average_len (List [2]) (List [[]]);;
val one : int = 1

将这两个定义分解成如下形式是很自然的

# let average f x y = (f x + f y) / 2;;
val average : ('a -> int) -> 'a -> 'a -> int = <fun>

但是,average len的类型比average_len的类型不那么通用,因为它要求第一个和第二个参数的类型相同

# average_len (List [2]) (List [[]]);;
- : int = 1
# average len (List [2]) (List [[]]);;
错误:此表达式的类型为 'a list,但期望表达式的类型为 int

与之前的多态递归一样,问题源于类型变量仅在let定义的开头引入。当我们计算f xf y时,xy的类型会统一在一起。为了避免这种统一,我们需要指示类型检查器f在其第一个参数中是多态的。从某种意义上说,我们希望average具有类型

val average: ('a. 'a nested -> int) -> 'a nested -> 'b nested -> int

请注意,此语法在OCaml中无效:average在其一个参数的类型内部具有普遍量化的类型'a,而对于多态递归,普遍量化的类型是在其余类型之前引入的。普遍量化类型的此位置意味着average是二阶多态函数。OCaml不直接支持这种高阶函数:二阶多态函数及更高阶函数的类型推断是不可判定的;因此,使用这种高阶函数需要手动处理这些普遍量化的类型。

在 OCaml 中,有两种方法可以引入这种显式的全称量化类型:全称量化记录字段,

# type 'a nested_reduction = { f:'elt. 'elt nested -> 'a };;
type 'a nested_reduction = { f : 'elt. 'elt nested -> 'a; }
# let boxed_len = { f = len };;
val boxed_len : int nested_reduction = {f = <fun>}

以及全称量化对象方法

# let obj_len = object method f:'a. 'a nested -> 'b = len end;;
val obj_len : < f : 'a. 'a nested -> int > = <obj>

为了解决我们的问题,我们可以使用记录解决方案

# let average nsm x y = (nsm.f x + nsm.f y) / 2 ;;
val average : int nested_reduction -> 'a nested -> 'b nested -> int = <fun>

或对象解决方案

# let average (obj:<f:'a. 'a nested -> _ > ) x y = (obj#f x + obj#f y) / 2 ;;
val average : < f : 'a. 'a nested -> int > -> 'b nested -> 'c nested -> int = <fun>