[Question] Functor sharing constraint

Learning
1

Hi :slight_smile:

I’d like to make a general queue , so I’m using functor to generate queue structure like Map.Make()

  1 module type QueueType = sig
  2   type t
  3 end
  4 
  5 module Int_Queue = struct
  6   type t = int list
  7 end
  8 
  9 module type Queue = sig
 10   type data
 11 
 12   val is_empty : data -> bool
 13 end
 14 
 15 module Make(Q : QueueType) : Queue with type data = Q.t = struct
 16   type data = Q.t
 17 
 18   let is_empty l = true
 19   (* I'd like to handle parameter l as int list like below *)
 20    (* let is_empty l =
 21      * match l with
 22      * | _::_ -> false
 23      * | _ -> true *)
 24 end;;
 25 let _ = module A = Make(Int_Queue);;

If is_empty() is changed to commented code, ocaml says type error. I think the type of module Make is already enforced with Q.t which is int list, so module Make should know its type but it seems to be not in my case

Let me know what I’m missing.

Thank you!

2

Hey there. Full disclamer, I’m no expert.

I think you mixed up the type of your queue and the type of your elements.

val is_empty : data -> bool

You use a queue there, so the type of your queue itself is data.

If you want to use the QueueType.t as the type of the elements in your queue, you wouldn’t expect it to always be a list. It would be some arbitrary type.
If you look at your Queue-signature, you see that you have an abstract type there as well. There is nothing mentioned of a list.
The list is part of the implementation, not of the signature for those that you use there.

You can use it in your Functor, and then only in there it’s known that the data is a list:

module Make(Q:QueueType) : Queue = struct
  type data = Q.t list
  let is_empty l = l = []
end

module IntQueue = Make(struct type t = int end)
1 Like
3

Hi @Splingush :slight_smile:

This question was inspired by Map.Make(). when I see the example of Map, it is beautiful because they provide the same logic as a given type of the key. So, I searched how it works and found the keyword that was functor and sharing constraints.

So, I’d like to implement simple anything like Map.Make() .

  1. Provide the same logic of Queue.
  2. Take module whose specified the which key type.

I implemented this feature without functor and sharing constraints using just one module and polymorphic type, but I’d like to experience functor and sharing constraints in my code.

4

You may be misreading the definition of your functor argument. When you write,

module Make(Q : QueueType) : Queue with type data = Q.t

you are stating that your functor works for any module Q that implements the specification QueueType, in other words for any module that define some black-box type t. At this point, there is no relationship at all between this type and any other type (like the type Int_queue.t).

If you wanted to express that the fact the type of the queue is a list of some elements, you need to add more information to your argument signature. Something like

module type Monomorphic_list = sig
  type elt
  type t = elt list
end
module Make(Q: Monomorphic_list): Queue with type data = Q.t  = struct
  type data = Q.t
  let is_empty = function [] -> true | _ -> false
end
2 Likes