如何满足 Comparable.S 我的类型

Question

我正在尝试为我的数据类型创建一个集合（使用 Core.Std.Set）作为文字，这样我就可以获得为我的子句类型使用集合的性能优势（而不是定义 type clause = literal list).

type atom = string

type sign = Pos | Neg

type literal = sign * atom

module Literal : sig
  type t = literal
  include Comparable.S with type t := t  
end = struct
  module T = struct
    type t = literal
    let compare t1 t2 =
      match (t1,t2) with
      | ((Pos,_), (Neg,_)) -> 1
      | ((Neg,_), (Pos,_)) -> -1
      | ((_,x), (_,y)) -> String.compare x y
  end
  include T
  include Comparable.Make(T)
end

module Clause = Set.Make(Literal)

我正在关注 Real World OCaml，Chapter 13. Maps and Hash Tables 在 满足 Comparable.S 接口 部分。问题是我们没有 sexp_of_t 和 t_of_sexp 函数。但是当我将 type t = literal 行更改为 type t = literal with sexp 时，编译器会说 Error: Unbound value literal_of_sexp.

这让我相信 (a) 我必须自己实现 sexp 函数（我不确定我将如何处理这个），或者 (b) 我不应该试图满足 Comparable.S 无论如何（出于某种原因，它只适用于原始类型）。

Answer 1

正在编写 type t = literal with sexp 请求为 t 生成函数，这将是 t_of_sexp 和 sexp_of_t。然而，这些函数的实现假定相应的函数可用于 literal，因为 t 是根据 literal 定义的。换句话说，您还需要将 with sexp 添加到 type literal = ... 上，这反过来又要求您对 sign 和 atom.

这样做

另请注意，您使用的是 camlp4，但许多工具（例如您使用的语法扩展）正在迁移到 ppx（RWO 书在这一点上已过时）。与 sexplib.syntax 支持的 with sexp 不同，我们鼓励您现在使用 ppx_sexp_conv 支持的 [@@deriving sexp]。

这是一个完整的工作示例：

$ cat foo.ml
open Core.Std

type atom = string [@@deriving sexp,compare]
type sign = Pos | Neg [@@deriving sexp,compare]
type literal = sign * atom [@@deriving sexp,compare]

module Literal : sig
  type t = literal [@@deriving sexp,compare]
  include Comparable.S with type t := t
end = struct
  module T = struct
    type t = literal [@@deriving sexp,compare]
  end
  include T
  include Comparable.Make(T)
end

module Clause = Set.Make(Literal)

您的 compare 函数非常好，但我还向您展示了如何使用 ppx_compare，它会生成 compare 函数。像这样编译：

$ ocamlfind ocamlc -package core,ppx_sexp_conv,ppx_compare -thread -c foo.ml

可以添加-dsource查看生成的代码。您不能按照 RWO 的建议使用 corebuild，因为它假定正在使用 camlp4，但这与 ppx 不兼容，因此您会收到错误消息。

Answer 2

首先，你仍然可以使用普通的旧camlp4。它没有被弃用，大多数编译器版本的大多数核心版本仍然需要它。不要害怕，您的代码将依赖于它，在需要时您可以自动将您的 camlp4 代码转换为 ppx 代码。到目前为止，我建议您坚持使用 camlp4.

使用 with 符号，您的代码可以重写为：

type atom = string with sexp,compare
type sign = Pos | Neg with sexp,compare
type literal = sign * atom with sexp,compare 

module Literal = struct
  type t = literal with sexp,compare
  include Comparable.Make(struct
      type nonrec t = t with sexp,compare
    end)
end

module Clause = Set.Make(Literal)

但是有一件事你应该知道。没有必要使用 Set.Make。 Comparable接口里面提供了集合和映射，所以，你应该这样写：

module Clause = Literal.Set

还有Literal.Map。如果您正在寻找哈希表和哈希集，那么您可以使用 Hashable 接口，这将为您提供 Literal.Table 和 Literal.Hash_set。您可以使用 Hashable.Make 仿函数来实现，并将其结果添加到 Literal 模块：

  include Hashable.Make(struct
      type nonrec t = t with sexp,compare
      let hash = Hashtbl.hash
    end)

您也可以使用 Identifiable 接口，它是 Comparable 和 Hashable 的总和。

如何满足 Comparable.S 我的类型

How to satisfy Comparable.S with my type

ocaml