时间戳

首页 > 解决方案 > 为什么这个 OCaml 仿函数不能识别结构类型？

types - 为什么这个 OCaml 仿函数不能识别结构类型？

问题描述

我编写了以下仿函数和实例，

module type Set = sig
  type elt
  type t
  val empty : t
  val insert : elt -> t -> t
  val find : elt -> t -> bool
end

module type OrderedSet = sig
  type t
  val compare : t -> t -> int
end

module BstSet(M: OrderedSet) : Set = struct
  type elt = M.t
  type t = M.t tree
  let empty = Leaf
  let rec insert x tr = match tr with
    | Leaf -> Node(Leaf, x, Leaf)
    | Node (lt, y, rt) -> let c = M.compare x y in
                          if c < 0 then Node (insert x lt, y, rt)
                          else if c > 0 then Node (lt, y, insert x rt)
                          else Node (lt, y, rt)
  let rec find x tr = match tr with
    | Leaf -> false
    | Node (lt, y, rt) -> let c = M.compare x y in
                          if c = 0 then true
                          else if c < 0 then find x lt
                          else find x rt
end

module MyString : OrderedSet = struct
  type t = string
  let compare s1 s2 = compare s1 s2
end

module StringSet = BstSet(MyString);;

StringSet.empty |> StringSet.insert "abc";;

并且编译器引发错误

StringSet.empty |> StringSet.insert "abc";;
                                          ^^^^^
Error: This expression has type string but an expression was expected of type
         StringSet.elt = BstSet(MyString).elt
Command exited with code 2.

这让我很困惑，因为我原以为编译器会发生这样的事情：

  1. 我们BstSet(MyString)用函子构造，所以参数M是MyString。
  2. 这意味着当我们称之为M.tis时string。
  3. 这意味着elt是string。
  4. 这意味着，在 for 的签名中insert，我们有一个函数string -> string tree -> string tree。

所以这应该编译。或者更直接地说，我原以为StringSet.elt会等于string。

标签： typesocaml

解决方案

定义

module BstSet(M: OrderedSet) : Set = struct ... end

Set.elt没有说明and之间的相等性 M.t（实际上，它们不需要相同，例如，实现可以将额外信息嵌入到 elt 类型中）。要表达这种平等，您必须添加共享约束，例如，

module BstSet(M: OrderedSet) : Set with type elt = M.t = struct ... end

或者，您可以删除模块类型并让编译器查看实现，例如，像这样

module BstSet(M: OrderedSet) = struct ... end

当您不打算从模块中导出仿函数并且仅将其用于内部目的时，这很有用。

推荐阅读