可以在 OCaml 中对类型之间的二进制函数进行编码吗？
Can one encode binary functions between types in OCaml?
我想知道是否可以在 OCaml 中构建类似于多重分派的东西。为此，我尝试为多方法的输入签名创建一个显式类型。例如，我定义了一个数字类型
type _ num =
| I : int -> int num
| F : float -> float num
现在我想要一个函数 add 对 'a num 和 'b num 以及 return 和 int num 求和，如果两者都 'a和 'b 是 int，如果其中至少一个是 float，则 float num。此外，类型系统应该知道输出将使用哪个构造函数。 IE。例如，应该在函数调用中静态知道输出的类型为 int num。
这可能吗？到目前为止，我只能管理一个签名函数 type a b. a num * b num -> a num，因此（更一般的）float 总是必须作为第一个参数提供。 int num * float num 这种情况必须被禁止，从而导致非详尽的模式匹配和运行时异常。
似乎需要像 type a b. a num * b num -> c(a,b) num 这样的签名，其中 c 是一个包含类型提升规则的类型函数。我不认为 OCaml 有这个。开放类型或对象是否能够捕捉到这一点？我不是在寻找类型之间最通用的函数，如果我能明确列出少数输入类型组合和相应的输出类型就足够了。
从 4.04.0 版本开始，OCaml 没有办法以这种方式对类型级依赖项进行编码。打字规则必须更简单。
一个选择是为此使用一个简单的变体类型，将所有内容包装成一个（可能很大的）类型并匹配：
type vnum =
| Int of int
| Float of float
let add_vnum a b =
match a, b with
| Int ia, Int ib -> Int (ia + ib)
| Int i, Float f
| Float f, Int i -> Float (float_of_int i +. f)
| Float fa, Float fb -> Float (fa +. fb)
另一种方法是限制输入值具有匹配的类型：
type _ gnum =
| I : int -> int gnum
| F : float -> float gnum
let add_gnum (type a) (x : a gnum) (y : a gnum) : a gnum =
match x, y with
| I ia, I ib -> I (ia + ib)
| F fa, F fb -> F (fa +. fb)
最后，输入值之一的类型可用于约束 return 值的类型。在此示例中，return 值将始终与第二个参数具有相同的类型：
type _ gnum =
| I : int -> int gnum
| F : float -> float gnum
let add_gnum' (type a b) (x : a gnum) (y : b gnum) : b gnum =
match x, y with
| I i1, I i2 -> I (i1 + i2)
| F f1, F f2 -> F (f1 +. f2)
| I i, F f -> F (float_of_int i +. f)
| F f, I i -> I (int_of_float f + i)
一个选项是使用带参数元组的子类型化，这允许重用一些代码（这就是使用子类型化的原因）：
type intpair = [`int_int of int * int]
type floatpair = [`float_float of float * float]
type num = [`int of int | `float of float]
type pair =
[ `float_int of float * int
| `int_float of int * float
| intpair | floatpair ]
let plus_int_int = function `int_int (i,j) -> `int (i+j)
let plus_float_float = function `float_float (x,y) -> `float (x+.y)
let plus_int_float = function `int_float (i,y) -> `float(float i +. y)
let plus_float_int = function `float_int (x,j) -> `float(x +. float j)
let plus
: pair -> num
= function
| `int_int _ as a -> plus_int_int a
| `float_float _ as a -> plus_float_float a
| `int_float _ as a -> plus_int_float a
| `float_int _ as a -> plus_float_int a
现在如果你想要静态保证，你需要使用 GADTs：
type 'a num =
| Int : int -> int num
| Float : float -> float num
type 'a binop =
| Intpair : (int * int) -> int binop
| Int_Float : (int * float) -> float binop
| Float_Int : (float * int) -> float binop
| Floatpair : (float * float) -> float binop
let plus :
type a . a binop -> a num
= function
| Intpair (a,b) -> Int (a+b)
| Int_Float (a,y) -> Float (float a +. y)
| Float_Int (x,b) -> Float (x +. float b)
| Floatpair (x,y) -> Float (x +. y)
您所询问的具体情况可以使用 GADT 和多态性很好地解决
变体。请参阅此代码底部对 M.add 的调用：
type whole = [ `Integer ]
type general = [ whole | `Float ]
type _ num =
| I : int -> [> whole ] num
| F : float -> general num
module M :
sig
val add : ([< general ] as 'a) num -> 'a num -> 'a num
val to_int : whole num -> int
val to_float : general num -> float
end =
struct
let add : type a. a num -> a num -> a num = fun a b ->
match a, b with
| I n, I m -> I (n + m)
| F n, I m -> F (n +. float_of_int m)
(* Can't allow the typechecker to see an I pattern first. *)
| _, F m ->
match a with
| I n -> F (float_of_int n +. m)
| F n -> F (n +. m)
let to_int : whole num -> int = fun (I n) -> n
let to_float = function
| I n -> float_of_int n
| F n -> n
end
(* Usage. *)
let () =
M.add (I 1) (I 2) |> M.to_int |> Printf.printf "%i\n";
M.add (I 1) (F 2.) |> M.to_float |> Printf.printf "%f\n";
M.add (F 1.) (I 2) |> M.to_float |> Printf.printf "%f\n";
M.add (F 1.) (F 2.) |> M.to_float |> Printf.printf "%f\n"
打印
3
3.000000
3.000000
3.000000
您不能将上述任何 to_float 更改为 to_int：它是静态的
已知仅添加两个 I 会导致 I。但是，您可以更改
to_int 到 to_float（并调整 printf）。这些操作很容易组合和传播类型信息。
嵌套 match 表达式的愚蠢行为是一种技巧，我会在
关于邮件列表。我以前从未见过这样做。
一般类型函数
据我所知，在当前 OCaml 中评估通用类型函数的唯一方法需要
用户提供见证，即一些额外的类型和价值信息。这个
可以通过多种方式完成，例如将参数包装在额外的构造函数中
（参见@mookid 的回答），使用 first-class 模块（也在接下来讨论
部分），提供一小部分抽象值供选择（其中
实现真正的操作，然后包装器分派给这些值）。这
下面的示例使用第二个 GADT 来编码有限关系：
type _ num =
| I : int -> int num
| F : float -> float num
(* Witnesses. *)
type (_, _, _) promotion =
| II : (int, int, int) promotion
| IF : (int, float, float) promotion
| FI : (float, int, float) promotion
| FF : (float, float, float) promotion
module M :
sig
val add : ('a, 'b, 'c) promotion -> 'a num -> 'b num -> 'c num
end =
struct
let add (type a) (type b) (type c)
(p : (a, b, c) promotion) (a : a num) (b : b num) : c num =
match p, a, b with
| II, I n, I m -> I (n + m)
| IF, I n, F m -> F (float_of_int n +. m)
| FI, F n, I m -> F (n +. float_of_int m)
| FF, F n, F m -> F (n +. m)
end
(* Usage. *)
let () =
M.add II (I 1) (I 2) |> fun (I n) -> n |> Printf.printf "%i\n";
M.add IF (I 1) (F 2.) |> fun (F n) -> n |> Printf.printf "%f\n"
这里，类型函数是('a, 'b, 'c) promotion，其中'a，'b是
参数，'c 是结果。不幸的是，你必须通过 add
promotion 的实例 'c 被磨碎，即像这样的东西不会
（据我所知）工作：
type 'p result = 'c
constraint 'p = (_, _, 'c) promotion
val add : 'a num -> 'b num -> ('a, 'b, _) promotion result num
尽管 'c 完全由 'a 和 'b 决定，但由于 GADT；编译器仍然认为它基本上只是
val add : 'a num -> 'b num -> 'c num
证人并没有真正让你相信只有四个功能，除了
操作集（add、multiply 等）和 argument/result 类型
组合，可以大部分相互正交；打字可以是
更好，事情可以稍微更容易使用和实施。
EDIT 实际上可以删除 I 和 F 构造函数，即
val add : ('a, 'b, 'c) promotion -> 'a -> 'b -> `c
这使得使用更简单：
M.add IF 1 2. |> Printf.printf "%f\n"
但是，在这两种情况下，这都不像 GADT+多态变体解决方案那样可组合，因为从未推断出见证。
未来的 OCaml：模块化隐式
如果你的witness是first-class模块，编译器可以帮你选择
自动使用模块化隐式。您可以在
4.02.1+modular-implicits-ber 切换。第一个示例只是将前面示例中的 GADT witnesses 包装在模块中，让编译器为您选择它们：
module type PROMOTION =
sig
type a
type b
type c
val promotion : (a, b, c) promotion
end
implicit module Promote_int_int =
struct
type a = int
type b = int
type c = int
let promotion = II
end
implicit module Promote_int_float =
struct
type a = int
type b = float
type c = float
let promotion = IF
end
(* Two more like the above. *)
module M' :
sig
val add : {P : PROMOTION} -> P.a num -> P.b num -> P.c num
end =
struct
let add {P : PROMOTION} = M.add P.promotion
end
(* Usage. *)
let () =
M'.add (I 1) (I 2) |> fun (I n) -> n |> Printf.printf "%i\n";
M'.add (I 1) (F 2.) |> fun (F n) -> n |> Printf.printf "%f\n"
使用模块化隐式，您还可以简单地添加未标记的浮点数和整数。此示例对应于调度到函数 "witness":
module type PROMOTING_ADD =
sig
type a
type b
type c
val add : a -> b -> c
end
implicit module Add_int_int =
struct
type a = int
type b = int
type c = int
let add a b = a + b
end
implicit module Add_int_float =
struct
type a = int
type b = float
type c = float
let add a b = (float_of_int a) +. b
end
(* Two more. *)
module M'' :
sig
val add : {P : PROMOTING_ADD} -> P.a -> P.b -> P.c
end =
struct
let add {P : PROMOTING_ADD} = P.add
end
(* Usage. *)
let () =
M''.add 1 2 |> Printf.printf "%i\n";
M''.add 1 2. |> Printf.printf "%f\n"
我想知道是否可以在 OCaml 中构建类似于多重分派的东西。为此，我尝试为多方法的输入签名创建一个显式类型。例如，我定义了一个数字类型
type _ num =
| I : int -> int num
| F : float -> float num
现在我想要一个函数 add 对 'a num 和 'b num 以及 return 和 int num 求和，如果两者都 'a和 'b 是 int，如果其中至少一个是 float，则 float num。此外，类型系统应该知道输出将使用哪个构造函数。 IE。例如，应该在函数调用中静态知道输出的类型为 int num。
这可能吗？到目前为止，我只能管理一个签名函数 type a b. a num * b num -> a num，因此（更一般的）float 总是必须作为第一个参数提供。 int num * float num 这种情况必须被禁止，从而导致非详尽的模式匹配和运行时异常。
似乎需要像 type a b. a num * b num -> c(a,b) num 这样的签名，其中 c 是一个包含类型提升规则的类型函数。我不认为 OCaml 有这个。开放类型或对象是否能够捕捉到这一点？我不是在寻找类型之间最通用的函数，如果我能明确列出少数输入类型组合和相应的输出类型就足够了。
从 4.04.0 版本开始，OCaml 没有办法以这种方式对类型级依赖项进行编码。打字规则必须更简单。
一个选择是为此使用一个简单的变体类型，将所有内容包装成一个（可能很大的）类型并匹配：
type vnum =
| Int of int
| Float of float
let add_vnum a b =
match a, b with
| Int ia, Int ib -> Int (ia + ib)
| Int i, Float f
| Float f, Int i -> Float (float_of_int i +. f)
| Float fa, Float fb -> Float (fa +. fb)
另一种方法是限制输入值具有匹配的类型：
type _ gnum =
| I : int -> int gnum
| F : float -> float gnum
let add_gnum (type a) (x : a gnum) (y : a gnum) : a gnum =
match x, y with
| I ia, I ib -> I (ia + ib)
| F fa, F fb -> F (fa +. fb)
最后，输入值之一的类型可用于约束 return 值的类型。在此示例中，return 值将始终与第二个参数具有相同的类型：
type _ gnum =
| I : int -> int gnum
| F : float -> float gnum
let add_gnum' (type a b) (x : a gnum) (y : b gnum) : b gnum =
match x, y with
| I i1, I i2 -> I (i1 + i2)
| F f1, F f2 -> F (f1 +. f2)
| I i, F f -> F (float_of_int i +. f)
| F f, I i -> I (int_of_float f + i)
一个选项是使用带参数元组的子类型化，这允许重用一些代码（这就是使用子类型化的原因）：
type intpair = [`int_int of int * int]
type floatpair = [`float_float of float * float]
type num = [`int of int | `float of float]
type pair =
[ `float_int of float * int
| `int_float of int * float
| intpair | floatpair ]
let plus_int_int = function `int_int (i,j) -> `int (i+j)
let plus_float_float = function `float_float (x,y) -> `float (x+.y)
let plus_int_float = function `int_float (i,y) -> `float(float i +. y)
let plus_float_int = function `float_int (x,j) -> `float(x +. float j)
let plus
: pair -> num
= function
| `int_int _ as a -> plus_int_int a
| `float_float _ as a -> plus_float_float a
| `int_float _ as a -> plus_int_float a
| `float_int _ as a -> plus_float_int a
现在如果你想要静态保证，你需要使用 GADTs：
type 'a num =
| Int : int -> int num
| Float : float -> float num
type 'a binop =
| Intpair : (int * int) -> int binop
| Int_Float : (int * float) -> float binop
| Float_Int : (float * int) -> float binop
| Floatpair : (float * float) -> float binop
let plus :
type a . a binop -> a num
= function
| Intpair (a,b) -> Int (a+b)
| Int_Float (a,y) -> Float (float a +. y)
| Float_Int (x,b) -> Float (x +. float b)
| Floatpair (x,y) -> Float (x +. y)
您所询问的具体情况可以使用 GADT 和多态性很好地解决
变体。请参阅此代码底部对 M.add 的调用：
type whole = [ `Integer ]
type general = [ whole | `Float ]
type _ num =
| I : int -> [> whole ] num
| F : float -> general num
module M :
sig
val add : ([< general ] as 'a) num -> 'a num -> 'a num
val to_int : whole num -> int
val to_float : general num -> float
end =
struct
let add : type a. a num -> a num -> a num = fun a b ->
match a, b with
| I n, I m -> I (n + m)
| F n, I m -> F (n +. float_of_int m)
(* Can't allow the typechecker to see an I pattern first. *)
| _, F m ->
match a with
| I n -> F (float_of_int n +. m)
| F n -> F (n +. m)
let to_int : whole num -> int = fun (I n) -> n
let to_float = function
| I n -> float_of_int n
| F n -> n
end
(* Usage. *)
let () =
M.add (I 1) (I 2) |> M.to_int |> Printf.printf "%i\n";
M.add (I 1) (F 2.) |> M.to_float |> Printf.printf "%f\n";
M.add (F 1.) (I 2) |> M.to_float |> Printf.printf "%f\n";
M.add (F 1.) (F 2.) |> M.to_float |> Printf.printf "%f\n"
打印
3
3.000000
3.000000
3.000000
您不能将上述任何 to_float 更改为 to_int：它是静态的
已知仅添加两个 I 会导致 I。但是，您可以更改
to_int 到 to_float（并调整 printf）。这些操作很容易组合和传播类型信息。
嵌套 match 表达式的愚蠢行为是一种技巧，我会在
关于邮件列表。我以前从未见过这样做。
一般类型函数
据我所知，在当前 OCaml 中评估通用类型函数的唯一方法需要 用户提供见证，即一些额外的类型和价值信息。这个 可以通过多种方式完成，例如将参数包装在额外的构造函数中 （参见@mookid 的回答），使用 first-class 模块（也在接下来讨论 部分），提供一小部分抽象值供选择（其中 实现真正的操作，然后包装器分派给这些值）。这 下面的示例使用第二个 GADT 来编码有限关系：
type _ num =
| I : int -> int num
| F : float -> float num
(* Witnesses. *)
type (_, _, _) promotion =
| II : (int, int, int) promotion
| IF : (int, float, float) promotion
| FI : (float, int, float) promotion
| FF : (float, float, float) promotion
module M :
sig
val add : ('a, 'b, 'c) promotion -> 'a num -> 'b num -> 'c num
end =
struct
let add (type a) (type b) (type c)
(p : (a, b, c) promotion) (a : a num) (b : b num) : c num =
match p, a, b with
| II, I n, I m -> I (n + m)
| IF, I n, F m -> F (float_of_int n +. m)
| FI, F n, I m -> F (n +. float_of_int m)
| FF, F n, F m -> F (n +. m)
end
(* Usage. *)
let () =
M.add II (I 1) (I 2) |> fun (I n) -> n |> Printf.printf "%i\n";
M.add IF (I 1) (F 2.) |> fun (F n) -> n |> Printf.printf "%f\n"
这里，类型函数是('a, 'b, 'c) promotion，其中'a，'b是
参数，'c 是结果。不幸的是，你必须通过 add
promotion 的实例 'c 被磨碎，即像这样的东西不会
（据我所知）工作：
type 'p result = 'c
constraint 'p = (_, _, 'c) promotion
val add : 'a num -> 'b num -> ('a, 'b, _) promotion result num
尽管 'c 完全由 'a 和 'b 决定，但由于 GADT；编译器仍然认为它基本上只是
val add : 'a num -> 'b num -> 'c num
证人并没有真正让你相信只有四个功能，除了
操作集（add、multiply 等）和 argument/result 类型
组合，可以大部分相互正交；打字可以是
更好，事情可以稍微更容易使用和实施。
EDIT 实际上可以删除 I 和 F 构造函数，即
val add : ('a, 'b, 'c) promotion -> 'a -> 'b -> `c
这使得使用更简单：
M.add IF 1 2. |> Printf.printf "%f\n"
但是，在这两种情况下，这都不像 GADT+多态变体解决方案那样可组合，因为从未推断出见证。
未来的 OCaml：模块化隐式
如果你的witness是first-class模块，编译器可以帮你选择
自动使用模块化隐式。您可以在
4.02.1+modular-implicits-ber 切换。第一个示例只是将前面示例中的 GADT witnesses 包装在模块中，让编译器为您选择它们：
module type PROMOTION =
sig
type a
type b
type c
val promotion : (a, b, c) promotion
end
implicit module Promote_int_int =
struct
type a = int
type b = int
type c = int
let promotion = II
end
implicit module Promote_int_float =
struct
type a = int
type b = float
type c = float
let promotion = IF
end
(* Two more like the above. *)
module M' :
sig
val add : {P : PROMOTION} -> P.a num -> P.b num -> P.c num
end =
struct
let add {P : PROMOTION} = M.add P.promotion
end
(* Usage. *)
let () =
M'.add (I 1) (I 2) |> fun (I n) -> n |> Printf.printf "%i\n";
M'.add (I 1) (F 2.) |> fun (F n) -> n |> Printf.printf "%f\n"
使用模块化隐式，您还可以简单地添加未标记的浮点数和整数。此示例对应于调度到函数 "witness":
module type PROMOTING_ADD =
sig
type a
type b
type c
val add : a -> b -> c
end
implicit module Add_int_int =
struct
type a = int
type b = int
type c = int
let add a b = a + b
end
implicit module Add_int_float =
struct
type a = int
type b = float
type c = float
let add a b = (float_of_int a) +. b
end
(* Two more. *)
module M'' :
sig
val add : {P : PROMOTING_ADD} -> P.a -> P.b -> P.c
end =
struct
let add {P : PROMOTING_ADD} = P.add
end
(* Usage. *)
let () =
M''.add 1 2 |> Printf.printf "%i\n";
M''.add 1 2. |> Printf.printf "%f\n"