Functor implementing polymorphic module type... Help!

Learning
, ,
1

OK, I’m asking this because it’s bugging me and distracting me from carrying on learning OCaml - so please help!

Here’s the signature of a polymorphic set type - yes, there should be more functions defined but we’ll get there…

open Base
open Core

module type PolySet = sig
  type 'a t

  val empty : 'a t

  val mem : 'a -> 'a t -> bool

  val add : 'a -> 'a t -> 'a t

  val elts : 'a t -> 'a list
end

Now in order to implement this with a list (a Core list) I need to make sure that 'a has some way of testing equality. I don’t want to know what 'a is yet - I just need to make sure it can be tested for equality. So I think that should look something like:

module type Equal = sig
  type t

  val equal : t -> t -> bool
end

module ListSet' (M : Equal) : PolySet with type 'a t := M.t list  = struct
  type 'a t = M.t list

  let empty = []

  let mem x xs = List.mem xs x ~equal:M.equal

  let add x s = x :: s

  let elts s =  s
end

Which was a bit of a struggle - but feels right… and yet:

Error: Signature mismatch:
       ...
       Values do not match:
         val mem : M.t -> M.t list -> bool
       is not included in
         val mem : 'a -> M.t list -> bool

Which is so close. So how do I tell the compiler that type 'a = M.t, when it knows that type 'a t = M.t list? What am I missing here?

2

Try adding type elt to PolySet, and use it instead of 'a everywhere, and change 'a t to just t, then you can write with type elt := ... to get the equality you want.

But your objective isn’t clear to me. Are you trying to reinvent Stdlib.Set.Make?

3

You can’t do exactly what you want (define a polymorphic set) but something close:

(*first your signature for set should be*)
module type Set = sig
  type t (*the type of the sets*)
  type elt (*the type of the elements*)

  val empty : t

  val mem : elt -> t -> bool

  val add : elt -> t -> t

  val elts : t -> elt list
end

and then use your implementation with this type annotation:

module ListSet (M : Equal) : Set with type elt = M.t = struct

 (* put your implementation as above*)

end

Maybe this post could help you to understand a little bit more.

4

My objective is purely educational! Just poking around and trying things out. If Stdlib.Set.Make has the interface I’m interested, should I take a look at the source?

5

… Yes, I’ve managed that work around, but thank you for confirming that it’s a good alternative.

I’ll get reading!

6

Cool. Sorry that I was terse, my question was basically just trying to understand if you were consciously avoiding functors for some reason. The high-level answer is that for this sort of thing (parameterize over a type which has some operations), functors are generally the best solution. Reading the source of Set.Make would be good, but just the interface is the part that is relevant to your question. Note that there is also the “Comparator”-based approach to containers, as implemented in Base. It has some advantages and disadvantages, but many people unfamiliar with functors find the resulting interface more natural. That approach does involve more type theoretic wizardry though.

1 Like
7

The issue is that when you have a module signature:

module type PolySet = sig
  type 'a t

  val empty : 'a t

  val mem : 'a -> 'a t -> bool

  val add : 'a -> 'a t -> 'a t

  val elts : 'a t -> 'a list
end

the type variable 'a does not mean “for some arbitrary type to be provided for by the implementation” but “for all types”, so your type 'a t = M.t list (where M.t is a user defined type) does not match. Hence the need for the approach that has been recommended to you.

1 Like
8

Honestly didn’t find your answer too terse at all - appropriately direct!

I thought I was using functors! Ha!

Well, I’ve read the source of Set.Make - which made sense (looks like the solution I’d write without using a polymorphic datatype for t). I also read Comparator, which made no sense whatsoever, so I’m going to ignore it.

Is the problem with using a polymorphic datatype that it can’t be ‘decomposed’ when it’s implemented? It can never be partially implemented?

9

From a certain point of view the solution is polymorphic, and is the good way to implement it.

Fully polymorphic types are functions from type to type, and functors are just a generalisation of this notion.

(*we embed base type in the module language *)
module type T = sig type t end

(*the polymorphic type `list` is just a functor*)
module ListF (A : T) = struct type t = A.t list end

In this case we can apply this functor to any type, but in your case we can only apply it to a type with an equality function, hence the solution.

1 Like
10

Ah - this is starting to make sense. So when I destructively set the type with 'a t := M.t list it fixes the 'a ts in the signature, but not the 'as - which are still unbounded. And cannot be fixed - the type of 'a t is a type which takes anything… and so the need for a seperate element type which can be implemented…

Yes, this makes sense. My thanks!

11

This is a good answer, and it’s going to give me something to mull over for a while. Thanks!

12

Yes, that’s basically it. To represent (in a module signature) “for some arbitrary type to be provided for by the module implementations”, rather than a type variable you need an abstract type in the signature, such as 'type t', combined as necessary with a 'with type t = ...' type equality qualification for the module implementations, for code using the module.

I think most people learning ocaml modules stub their toe on this at some point, particularly those who have used C++ templates. I certainly did. ML’s type system takes a little getting used to.

1 Like