存在量化类型参数、递归函数和类型错误
Existentially quantified type parameter, recursive function and type error
考虑以下 OCaml 代码:
type mytype = My : 'a list * 'a -> mytype
let rec foo : int -> mytype =
fun n -> if n < 0 then My([], 2)
else let My(xs, y) = foo (n - 1)
in My(3::xs, y)
OCaml 解释器在 foo
的最后一行给我一个错误,
说:
This expression has type a#1 list but an expression was
expected of type int list
Type a#1 is not compatible with type int
我可以通过向 mytype
添加一个类型参数来使该代码工作,所以它将是
type _ mytype = My : 'a list * 'a -> 'a mytype
let rec foo : int -> 'a mytype =
...
但是假设我真的不想改变 mytype
的定义。然后我可以写 foo
,假设我想保留该函数的(非工作代码直观理解的)行为吗?
此外,有人可以解释问题的根源是什么,即为什么初始代码不进行类型检查?
当对 mytype
值进行模式匹配时,无法知道内部是什么类型。问题是,打字系统的行为非常简单,即使它来自递归调用,也不会试图知道 mytype 的来源(打字系统不会那样工作)。
问题是,你知道在那种情况下 'a
确实是 int
,但你需要向编译器提供证明。
在那种特定情况下,您不需要这样做。您只需要在函数结束时使用 GADT:
let foo n =
let rec aux n =
if n < 0 then ([], 2)
else let (xs, y) = aux (n - 1)
in (3::xs, y)
in
let (xs,y) = aux n in My (xs,y)
值得注意的是,使用该类型定义,您无法使用您知道 mytype
中存在整数值这一事实,因此它将非常不可用。 GADT 应仅在特定情况下使用,您应该确切地知道为什么以及如何使用它们。
编辑:
类型可以看作是附加到每个值的逻辑公式。在大多数情况下,它非常简单,您不必担心,主要是因为类型变量('a
'b
等等)是 普遍量化的 并且始终对类型的外部可见。
type 'a mylist = Cons of 'a * 'a list | Nil
(* should be read as:
for all 'a,
'a mylist is either
* a cons containing the same 'a and 'a list
* nil *)
type mylist = Cons : 'a * mylist -> mylist | Nil : mylist
(* should be read as:
mylist is either
* for some 'a, a 'a and another list
* nil *)
在上面的 GADT 中,您可以看到没有任何内容表明列表中的每个元素都属于同一类型。事实上,如果你得到一个mylist
,你无法知道里面是什么元素。
所以,你需要证明它。这样做的一个好方法是在 gadt 中存储类型证明:
type _ proof =
| Int : int proof
| Float : float proof
| Tuple : 'a proof * 'b proof -> ('a * 'b) proof
(* You can add other constructors depending on
the types you want to store *)
type mytype = My : 'a proof * 'a list * 'a -> mytype
现在有了这个,当打开一个mytype
时,你可以在证明上匹配来证明'a的值。编译器会知道它是相同的,因为它会在没有与正确类型相对应的证明的情况下拒绝创建 mytype。
正如您所见,GADT 并不简单,您经常需要在实施之前先做几份草稿。大多数时候,您可以避免使用它们(如果您不确定它们的工作原理,则根本不要使用它们)。
考虑以下 OCaml 代码:
type mytype = My : 'a list * 'a -> mytype
let rec foo : int -> mytype =
fun n -> if n < 0 then My([], 2)
else let My(xs, y) = foo (n - 1)
in My(3::xs, y)
OCaml 解释器在 foo
的最后一行给我一个错误,
说:
This expression has type a#1 list but an expression was expected of type int list
Type a#1 is not compatible with type int
我可以通过向 mytype
添加一个类型参数来使该代码工作,所以它将是
type _ mytype = My : 'a list * 'a -> 'a mytype
let rec foo : int -> 'a mytype =
...
但是假设我真的不想改变 mytype
的定义。然后我可以写 foo
,假设我想保留该函数的(非工作代码直观理解的)行为吗?
此外,有人可以解释问题的根源是什么,即为什么初始代码不进行类型检查?
当对 mytype
值进行模式匹配时,无法知道内部是什么类型。问题是,打字系统的行为非常简单,即使它来自递归调用,也不会试图知道 mytype 的来源(打字系统不会那样工作)。
问题是,你知道在那种情况下 'a
确实是 int
,但你需要向编译器提供证明。
在那种特定情况下,您不需要这样做。您只需要在函数结束时使用 GADT:
let foo n =
let rec aux n =
if n < 0 then ([], 2)
else let (xs, y) = aux (n - 1)
in (3::xs, y)
in
let (xs,y) = aux n in My (xs,y)
值得注意的是,使用该类型定义,您无法使用您知道 mytype
中存在整数值这一事实,因此它将非常不可用。 GADT 应仅在特定情况下使用,您应该确切地知道为什么以及如何使用它们。
编辑:
类型可以看作是附加到每个值的逻辑公式。在大多数情况下,它非常简单,您不必担心,主要是因为类型变量('a
'b
等等)是 普遍量化的 并且始终对类型的外部可见。
type 'a mylist = Cons of 'a * 'a list | Nil
(* should be read as:
for all 'a,
'a mylist is either
* a cons containing the same 'a and 'a list
* nil *)
type mylist = Cons : 'a * mylist -> mylist | Nil : mylist
(* should be read as:
mylist is either
* for some 'a, a 'a and another list
* nil *)
在上面的 GADT 中,您可以看到没有任何内容表明列表中的每个元素都属于同一类型。事实上,如果你得到一个mylist
,你无法知道里面是什么元素。
所以,你需要证明它。这样做的一个好方法是在 gadt 中存储类型证明:
type _ proof =
| Int : int proof
| Float : float proof
| Tuple : 'a proof * 'b proof -> ('a * 'b) proof
(* You can add other constructors depending on
the types you want to store *)
type mytype = My : 'a proof * 'a list * 'a -> mytype
现在有了这个,当打开一个mytype
时,你可以在证明上匹配来证明'a的值。编译器会知道它是相同的,因为它会在没有与正确类型相对应的证明的情况下拒绝创建 mytype。
正如您所见,GADT 并不简单,您经常需要在实施之前先做几份草稿。大多数时候,您可以避免使用它们(如果您不确定它们的工作原理,则根本不要使用它们)。