签名不匹配 'a list -> 'a Core.Std.List.t 不包含在 'a list -> 'a t

Question

我正在写《More Ocaml》一书的第11章，你尝试以各种方式实现一个集合。这段代码主要来自书中，但我已将其更改为使用Core（和Core's List）而不是stdlib。

open Core.Std;;
open Printf;;
module SetList :
  sig
    type 'a t;;
    val set_of_list : 'a list -> 'a t;;
    val list_of_set : 'a t -> 'a list;;
    val insert : 'a -> 'a t -> 'a t;;
    val size : 'a t -> int;;
    val member : 'a t -> 'a -> bool;;
  end
=
  struct
    type 'a t = 'a list;;
    let member = List.mem ~equal:(=);;
    let insert x l = if member l x then l else x::l;;
    let rec set_of_list l = match l with
      [] -> []
      |h::t -> insert h (set_of_list t);;
    let list_of_set x = x;;
    let size = List.length;;
  end;;

这给了我一个错误Values do not match: val set_of_list : '_a list -> '_a Core.Std.List.t is not included in val set_of_list : 'a list -> 'a t.

第一个问题，我该怎么做才能修复该错误？其次，更重要的是，为什么编译器没有意识到'a Core.Std.List.t等于'a t并且与第 15 行给定定义的值匹配。

Answer 1

你误会了错误。如果我们给出选项 -short-path（在给出类型错误时尝试找到最小的类型别名），我们会得到以下错误：

   Values do not match:
     val set_of_list : '_a t -> '_a t
   is not included in
     val set_of_list : 'a t -> 'a t

所以Core.Std.List.t确实等于t，编译器也看到了。问题出在偷偷摸摸的_.

错误的原因是所谓的值限制。基本上，类型检查器只有在绑定值时才能泛化（选择最通用的类型）。在您的情况下，剔除是member的定义。

如果以这种方式定义它，错误就会消失：

let member x = List.mem ~equal:(=) x

列表绑定到名称，因此类型检查器可以泛化。

当编译器不能时，它会生成一个"未知但非多态"的类型变量（我们称它们为单态），并将_添加到名称中。类型变量在首次使用时将是专用的。您可以尝试在顶层使用let r = ref None以更仔细地查看它。

Answer 2

您遇到值限制，需要 eta 扩展您的函数，例如，

let member lst = List. ~equal:(=) lst

关于值限制（也就是SO中的弱类型多态性）有很多问题和答案，所以我认为快速搜索会揭示更多信息。

'a Core.Std.List.t是'a list的类型同义词，所以那里不会有问题。应该为您敲响警钟的部分是类型 '_a 中的这个激烈的下划线。这称为弱类型变量。