Map type with `int list` as a key type

Learning
1

Hello all,

Is there a way to make Batteries’ Map type having int list as its key type?

I was expecting something like

open Batteries
IntList = List.Make(Int)
IntListMap = Map.Make(IntList)

but List does not have Make.

2

IDK about Batteries’ specifics, but you could always roll your own module that implements the required interface. I’ll give examples from Stdlib:

(* The type of Map.Make functor *)
Map.Make : OrderedType -> sig ... end

(* and this is what OrderedType stands for *)
module type OrderedType = sig
  type t
  val compare : t -> t -> int
end

(* let's implement OrderedType for int list *)
module IntListMap = Map.Make (struct
  type t = int list
  let compare = List.compare Int.compare
end)

To inspect values such as Map.Make and Map.OrderedType, you can use the #show REPL directive.
Hope this helps!

2 Likes
3

Hello!

I could be mistaken, but it seems that you may be confused about functors.

Let’s open up utop.

First, load the package.

#require "batteries" ;;

Next, let’s inspect the interface of the Batteries.Map.Make functor:

#show Batteries.Map.Make ;;

There’s a lot there, but at the top there’s

module Make : functor ( Ord : BatInterfaces.OrderedType ) -> ...

What this means is that Batteries.Map.Make is a functor of a single module argument called Ord. Ord may be any module that satisfies the module signature BatInterfaces.OrderedType.

What’s that?

#show BatInterfaces.OrderedType ;;

It’s

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

That is, Ord is any module that defines a type t and which has a function compare operating on two instances of t and returning an int.

So, what’s happening?

A module implementing an ordered map requires a key type that has an ordering relation. You specify the type and the ordering relation via the functor argument and the resulting module is “specialized” to the key type you provided.

To get a module which operates on keys of type int list you could write:

module Key = struct
  type t = int list
  let compare = List.compare Int.compare
end

module MyMap = Batteries.Map.Make (Key)

I hope that helps a little bit.

2 Likes