CODEWITHSUNDEEP
ocaml
Tom
Tom

Reputation: 208

How to satisfy Comparable.S with my type

I am trying to make a set (using Core.Std.Set) of my datatype for a literal, so that I can have the performance benefits of using sets for my clause type (rather than defining 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)

I was following Real World OCaml, Chapter 13. Maps and Hash Tables at the Satisfying the Comparable.S Interface section. The problem is that we don't have the sexp_of_t and t_of_sexp functions. But when I change the type t = literal line to type t = literal with sexp the compiler says Error: Unbound value literal_of_sexp.

This leads me to believe either (a) I have to implement the sexp functions myself (I'm not sure how I'd approach this), or (b) I shouldn't be trying to satisfy Comparable.S anyway (for some reason like it would only work for primitive types).

Upvotes: 1

Views: 607

Answers (2)

Ashish Agarwal
Ashish Agarwal

Reputation: 3030

Writing type t = literal with sexp requests to generate functions for t, which will be t_of_sexp and sexp_of_t. However, the implementations of these functions assume that corresponding functions are available for literal because t is defined in terms of literal. In other words you also need to add with sexp onto type literal = ..., which will in turn require you to do so for sign and atom.

Also note that you're using camlp4, but many tools such as the syntax extensions you're using are migrating to ppx (the RWO book is out of date on this point). Instead of with sexp as supported by sexplib.syntax, you are encouraged to now do [@@deriving sexp] as supported by ppx_sexp_conv.

Here's a complete working example:

$ 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)

Your compare function is perfectly fine, but I'm also showing you how to use ppx_compare, which generates compare functions. Compile like this:

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

You can add -dsource to view the generated code. You can't use corebuild as RWO recommends because it assumes camlp4 is being used, but that is incompatible with ppx, so you'll get an error.

Upvotes: 1

ivg
ivg

Reputation: 35210

First of all, you can still use plain old camlp4. It is not deprecated, and most of core versions on most of compiler versions still require it. And don't be afraid, that your code will depend on it, when needed you can automatically translate you camlp4 code to a ppx code. So far, I would recommend you to stick with camlp4.

Using with notation, your code can be rewritten as:

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)

But there is one thing, that you should know. There is no need to use Set.Make. Comparable interface provides sets and maps inside, so, you should write:

module Clause = Literal.Set

there is also Literal.Map. If you're looking for hash tables and hash sets, then you Hashable interface, that will give you Literal.Table and Literal.Hash_set. You can implement using Hashable.Make functor, and adding its result to the Literal module:

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

Also you can use Identifiable interface that is a sum of Comparable and Hashable.

Upvotes: 2

Related Questions