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

Question

我正在写书 "More Ocaml" 的第 11 章，您会在其中尝试以各种方式实现集合。此代码主要来自本书，但我将其更改为使用 Core（和 Core 的列表）而不是 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

您遇到了价值限制，需要对您的函数进行 eta 扩展，例如，

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

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

'a Core.Std.List.t 是 'a list 的类型同义词，因此不会有任何问题。应该提醒您的部分是 '_a 类型中的粗下划线。这被称为弱类型变量。

Answer 2

你错了。如果我们提供选项 -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，编译器会看到这一点。问题出在偷偷摸摸的 _.

错误的原因是所谓的值限制。基本上，只有当一个值被绑定时，类型检查器才能概括（选择最一般的类型）。在您的情况下，cullprint 是 member.

的定义

如果您这样定义，错误就会消失：

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

该列表绑定到一个名称，因此类型检查器可以概括。

当编译器不能时，它会产生一个类型变量"unknown but not polymorphic"（我们称它们为单态）并在名称中添加_。类型变量将在第一次使用时专门化。您可以尝试在顶层使用 let r = ref None 来更仔细地查看它。

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

Signature mismatch 'a list -> 'a Core.Std.List.t is not included in 'a list -> 'a t

ocaml

ocaml-core