Requiring specific "traits" from type variable

Learning
1

Hello, I’m trying to make a simple dictionary interface with multiple implementations. I imagine that I should declare a signature like this:

module type Dictionary = sig
  type ('k, 'v) t
  val create: unit -> ('k, 'v) t
  val get: ('k, 'v) t -> 'k -> 'v option
  val set: ('k, 'v) t -> 'k -> 'v -> unit
end

And then I can provide a Dictionary implementation like this (LinkedList implementation is skipped for brevity, should be irrelevant for the question):

module LinkedListDictionary : Dictionary = struct
  type ('k, 'v) t = ('k * 'v) LinkedList.t

  let create = LinkedList.create

  let get t k = Option.(
      LinkedList.find t ~f:(Fn.compose ??? fst) >>| Fn.compose snd LinkedList.value
    )

  let set t k v = LinkedList.insert_first t (k, v) |> ignore
end

Notice ??? in get. I expect here to be a call to 'k-specific equal call, and, in other implementations, also a call to 'k-specific hash function.

Of course, I can ask the user to provide equal/hash on each call, but I’m pretty sure OCaml supports more elegant solution. Could it be achieved with functors? Any other techniques? Or is what I am trying to achieve non-idiomatic and I should consider a totally different way of defining interface + implementations?

2

Have you taken a look at the Map module in the standard library? That’s the usual technique for what you’re trying to do.

3

Thanks for the hint! Do I understand correctly that technique is to have key’s type not as a type variable, but as a separate abstract type, and then provide it via a functor?

(Sorry if I’m asking obvious things, just started to learn how to work with modules)

4

Yes, I think that’s a reasonable way to put it. Usually we say that the Map.Make functor takes a module (with keys) of the specified type, and gives a map module which can handle keys of the given type. Parametric polymorphism is achieved by having functors re-use input modules in a generic way.

1 Like
5

If you don’t mind, I have some further questions. I went ahead and changed Dictionary signature:

module type Dictionary = sig
  type key
  type 'a t
  val create: unit -> 'a t
  val get: 'a t -> key -> 'a option
  val set: 'a t -> key -> 'a -> unit
end

Then I implemented a functor for making a LinkedList-based Dictionary:

module MakeLinkedListDictionary (Cmp: Comparable.S): (Dictionary with type key = Cmp.t) = struct
  type key = Cmp.t
  type 'a t = (key * 'a) LinkedList.t

  let create = LinkedList.create

  let get t k = Option.(
      LinkedList.find t ~f:(Fn.compose (Cmp.equal k) fst) >>| Fn.compose snd LinkedList.value
    )

  let set t k v = LinkedList.insert_first t (k, v) |> ignore
end

So far so good, code like this works fine:

let () =
  let module Dict = MakeLinkedListDictionary(String) in
  Dict.(
    let dict = create() in
    set dict "a" "b";
    match get dict "a" with
    | None -> printf "Not found value for key 'a', but should\n"
    | Some x -> printf "Found value for key 'a': %s\n" x;
      match get dict "b" with
      | None -> printf "Not found value for key 'b', as expected\n"
      | Some x -> printf "Found value for key 'b', but shouldn't : %s\n" x;
  ) |> ignore

Now I want to make following code work:


let test_dictionary dict = ???.(
    set dict "a" "b";
    match get dict "a" with
    | None -> printf "Not found value for key 'a', but should\n"
    | Some x -> printf "Found value for key 'a': %s\n" x;
      match get dict "b" with
      | None -> printf "Not found value for key 'b', as expected\n"
      | Some x -> printf "Found value for key 'b', but shouldn't : %s\n" x;
  ) 

let () =
  let module Dict = MakeLinkedListDictionary(String) in
  test_dictionary(Dict.create())

My question is what should I replace ??? with so test_dictionary will be specific about key type (String in this case), but abstract about LinkedList, so it would work in potential scenario like this

let () =
  let module Dict = MakeLinkedListDictionary(String) in test_dictionary(Dict.create());
  let module Dict = MakeTreeDictionary(String) in test_dictionary(Dict.create());
6

The answer is: you need another functor :slight_smile:

test_dictionary needs to be defined inside a scope (in this case a functor) which is given a module (let’s call it D) that is a Dictionary with type key = string. Now D is concrete in the key type (string) but abstract in the dictionary implementation.

I hope this helps!

1 Like
7

Yes, it does, thank you! Works like a charm. Now I see why people praise OCaml’s module system.

1 Like