将 GADT 转换为虚拟类型
Converting GADT to phantom types
我在玩 OCaml 中的 GADT 和幻像类型。我知道 GADT 是描述某些类型的幻像类型的便利工具——如果我错了请纠正我。所以我决定尝试将使用 GADT 类型的程序转换为使用 ADT 和 phantom 类型的程序。
我以 this blog post 的 GADT 程序作为起点。这是一个小型 bool/int 表达式求值器,这是它的要点:
module GADT = struct
type _ value =
| Bool : bool -> bool value
| Int : int -> int value
type _ expr =
| Value : 'a value -> 'a expr
| If : bool expr * 'a expr * 'a expr -> 'a expr
| Eq : 'a expr * 'a expr -> bool expr
| Lt : int expr * int expr -> bool expr
let rec eval : type a. a expr -> a = function
| Value (Bool b) -> b
| Value (Int i) -> i
| If (b, l, r) -> if eval b then eval l else eval r
| Eq (a, b) -> eval a = eval b
| Lt (a,b) -> a < b
end
所以我开始将其转换为ADT + phantom类型如下:
module ADT = struct
type 'a value =
| Bool of bool
| Int of int
let _Bool b : bool value = Bool b
let _Int i : int value = Int i
type 'a expr =
| Value of 'a value
| If of bool expr * 'a expr * 'a expr
| Eq of 'a expr * 'a expr
| Lt of int expr * int expr
let _Value v : 'a expr = Value v
let _If (cond, cons, alt) : 'a expr = If (cond, cons, alt)
let _Eq (left, right) : bool expr = Eq (left, right)
let _Lt (left, right) : bool expr = Lt (left, right)
let rec eval : type a. a expr -> a = function
| Value (Bool b) -> b
| Value (Int i) -> i
| If (cond, cons, alt) -> if eval cond then eval cons else eval alt
| Eq (left, right) -> eval left = eval right
| Lt (left, right) -> left < right
end
您无法控制 ADT 构造函数的类型变量,因此我创建了自己的 _Bool
、_Int
等构造函数来强制使用必要的类型。
但是,我的 ADT
模块无法编译:
let rec eval : type a. a expr -> a = function
| Value (Bool b) -> b
^
Error: This expression has type bool but an expression was expected of type a
此时我假设我的想法是有缺陷的,你不能通过这种方式将 GADT 转换为 ADT。但是我想听听在这个话题上更有经验的人。
没有 GADT 就无法做到这一点,因为幻像类型不能作为编译器的见证,表达式具有特定类型,因为有了幻像类型,您实际上可以执行以下操作:
let bool b : int value = Bool b;;
val bool : bool -> int value = <fun>
这就是为什么只有幻像类型是不够的,这就是为什么在 OCaml 中引入了 GADT。
我在玩 OCaml 中的 GADT 和幻像类型。我知道 GADT 是描述某些类型的幻像类型的便利工具——如果我错了请纠正我。所以我决定尝试将使用 GADT 类型的程序转换为使用 ADT 和 phantom 类型的程序。
我以 this blog post 的 GADT 程序作为起点。这是一个小型 bool/int 表达式求值器,这是它的要点:
module GADT = struct
type _ value =
| Bool : bool -> bool value
| Int : int -> int value
type _ expr =
| Value : 'a value -> 'a expr
| If : bool expr * 'a expr * 'a expr -> 'a expr
| Eq : 'a expr * 'a expr -> bool expr
| Lt : int expr * int expr -> bool expr
let rec eval : type a. a expr -> a = function
| Value (Bool b) -> b
| Value (Int i) -> i
| If (b, l, r) -> if eval b then eval l else eval r
| Eq (a, b) -> eval a = eval b
| Lt (a,b) -> a < b
end
所以我开始将其转换为ADT + phantom类型如下:
module ADT = struct
type 'a value =
| Bool of bool
| Int of int
let _Bool b : bool value = Bool b
let _Int i : int value = Int i
type 'a expr =
| Value of 'a value
| If of bool expr * 'a expr * 'a expr
| Eq of 'a expr * 'a expr
| Lt of int expr * int expr
let _Value v : 'a expr = Value v
let _If (cond, cons, alt) : 'a expr = If (cond, cons, alt)
let _Eq (left, right) : bool expr = Eq (left, right)
let _Lt (left, right) : bool expr = Lt (left, right)
let rec eval : type a. a expr -> a = function
| Value (Bool b) -> b
| Value (Int i) -> i
| If (cond, cons, alt) -> if eval cond then eval cons else eval alt
| Eq (left, right) -> eval left = eval right
| Lt (left, right) -> left < right
end
您无法控制 ADT 构造函数的类型变量,因此我创建了自己的 _Bool
、_Int
等构造函数来强制使用必要的类型。
但是,我的 ADT
模块无法编译:
let rec eval : type a. a expr -> a = function
| Value (Bool b) -> b
^
Error: This expression has type bool but an expression was expected of type a
此时我假设我的想法是有缺陷的,你不能通过这种方式将 GADT 转换为 ADT。但是我想听听在这个话题上更有经验的人。
没有 GADT 就无法做到这一点,因为幻像类型不能作为编译器的见证,表达式具有特定类型,因为有了幻像类型,您实际上可以执行以下操作:
let bool b : int value = Bool b;;
val bool : bool -> int value = <fun>
这就是为什么只有幻像类型是不够的,这就是为什么在 OCaml 中引入了 GADT。