How to initialize a Base.Hashtbl on an abstract type?

Learning
1

Could someone show me how to initialize a Base.Hashtbl and how to satisfy it with a key that is an abstracted list of ints? I tried lots of things but still fail to make it work and I don’t kow where to read (yes, did read the chapter in dev.RWO and JS docs as far as I thought makes sense)

So, what I have is something like this:

module MyModule : sig
    type t
end = struct
    type t = int list
end

What do I need to do in order to make it work with Hashtbl.create (module MyModule)

I tried various things like including Hashable.S in the signature, but I failed miserably.

2

Given MyModule, if you try to create a Hashtbl there’s this error:

utop # let table = Base.Hashtbl.create (module MyModule);;
Error: Signature mismatch:
       ...
       The value `hash' is required but not provided
       File "src/hashtbl_intf.ml", line 15, characters 2-21:
         Expected declaration
       The value `sexp_of_t' is required but not provided
       File "src/hashtbl_intf.ml", line 9, characters 4-49:
         Expected declaration
       The value `compare' is required but not provided
       File "src/hashtbl_intf.ml", line 8, characters 4-31:
         Expected declaration

Note that it requires MyModule to implement hash, sexp_of_t, and compare functions, i.e. implementing Base__.Hashtbl_intf.Key interface.

That said, do you really need to have MyModule as the key? If MyModule is the value, then you don’t need to give MyModule to create and instead provide modules such as Int (if your keys are ints) or String (if your keys are strings). Edit: sorry I reread your original post and you seem to really need it to be key, then you need to implement those functions.

3

Yeah, I already saw the error, but I fail to satisfy it as I both have to write the proper types in the signature and in the struct and I fail to do that.

I’m sure there is a shortcut by including some module in the signature and then defining the three functions but I can’t figure it out.

4

My ppx_deriving-fu is not that good, but afaik you can utilize ppx_compare and ppx_sexp_conv so that you can write:

module MyModule : sig
    type t [@@deriving compare, sexp_of]
    val hash : t -> int
end = struct
    type t = int list [@@deriving compare, sexp_of]
    let hash v = ... (*impl*)
end

Where you already get compare and sexp_of_t generated automatically by the ppx.

5

Yeah, this works so far (already had it) but I can’t seem to derive the hash. I find some places on the web where they mention [@@deriving hash] which is available via ppx_hash opam package, but I get error when I try to use it.

Error: Ppxlib.Deriving: 'hash' is not a supported signature type deriving generator

So I still don’t know what is the proper signature for my module.
Also, if possible, I’d very much like to see a solution without using PPX, as I want to understand what is the proper typing here.

6

Do you have ppx_hash as a dependency?

There’s nothing magical here – it’s just a bunch of boilerplate, which is why it’s so useful to have the ppx’s do it. I imagine you could use a dummy sexp_of_t function unless you’re trying to serialize your data structure; compare is just the usual loop over values with comparison of each int, and hash is generally just going to loop over the list and xor with a hash function per value. In the case of integers, it might even be xor-ing the actual integer value.

7

Yes, it “works” (or at least compiles) in the struct of the module, but not in the signature. Though it still doesn’t allow me to use the module as a Hashtbl key while complaining with the above errors.

8

An answer specific to your question is:

module MyModule : sig 
    type t [@@deriving compare, hash, sexp_of]
end = struct 
    type t = int list [@@deriving compare, hash, sexp_of]
end

module Table = Hashtbl.Make(MyModule)

However, the idiomatic approach is to automatically derive all other data types, including maps, sets, hash_sets, etc, instead of implementing each one manually. You can do this with the Identifiable.Make function, that derive a module that implements the Identifiable.S interface, from the provided minimal representation, e.g.,

module MyModule : sig 
    type t 
    include Idenfiable.S with type t := t
end = struct 
    module Base = struct 
       type t = int list [@@deriving bin_io, compare, hash, sexp]
       let of_string x = failwith "implement-me"
       let to_string x = failwith "implement-me"
       let module_name = "My_unit.MyModule"
    end
    include Base
    include Identifiable.Make(Base)
end

The Identifiable.S interface is very rich, so you may choose something smaller, like Identifiable.S_plain, Comparable.S, Comparable.S_plain, etc.

Also, when a deriver is not recognized, then you need to install it via opam and specify in the build system.

2 Likes