CODEWITHSUNDEEP
moduleocamlfunctor
Pteromys
Pteromys

Reputation: 1491

In OCaml, is it possible to define Map in terms of Set?

I have implemented a representation of sets (balanced search trees) in OCaml. It's actually a functor Make of signature

module Make :
  functor (T : ORDERED_TYPE) ->
sig
  type elt = T.t
  type t
  val empty : t
  val cons : elt -> t -> t
  val delete : elt -> t -> t
  val mem : elt -> t -> bool
  val cardinal : t -> int
end

where

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

Now I'd like to implement a dictionary like Map in the standard library. It has to have a signature like

 module Make: functor (T : ORDERED_TYPE) -> sig
    type key = T.t
    type +'a t
    ...
 end

where t is the type of dictionaries.

Implementing balanced search trees again is not elegant, so I want to define dictionaries in terms of sets implemented as a functor above. Can I do that?

Upvotes: 5

Views: 1280

Answers (4)

lambdapower
lambdapower

Reputation: 1032

Well, there actually IS an equal operator in there -- the compare function from the ordered type.

So define your own module for a key/value type that only takes into comparison the key-part:

module Keyvalue = struct
   type t = ('a * 'b)
   let compare x y = Pervasives.compare (fst x) (fst y)
end

and you are done. The problem now is, that your Set does not allow you to get its values; there is no get nor a fold function -- which imho is really limiting for such a data structure. If you are allowed to fumble with the Set implementation, you need to add a get function:

module Set = sig
   ...
   get : t -> elt -> elt
end

that will return the just asked for element. If you take the second element of the returned tuple, you have your value from the original key/value pair.

Upvotes: 0

Andreas Rossberg
Andreas Rossberg

Reputation: 36118

As others have already pointed out, there are at least two reasons why you cannot implement the requested map functor on top of the given set:

  1. The set signature provides no way to find an "equal" element in a given set.
  2. And even if it did, you could not store values in there polymorphically, as the type 'a map seems to require.

Are you sure that the task requires you to implement maps on top of sets? Maybe you are just supposed to implement them like sets?

Upvotes: 2

gasche
gasche

Reputation: 31479

As Jeffrey noted, you Set interface is not expressive enough to conveniently implement Map on top of it. It would be simpler to implement Set from Map, by defining sets as maps from keys to unit value.

Another possibility, that I would recommend, is to first expose a module of balanced search trees with no encapsulation, with the sole purpose of providing an efficient data structure, that is entirely revealed by the interface. You are then free to reuse it for any data structure you like, including Map and Set, without having to play games to define one in term of the other. This may not be terribly important in this case (defining Set from Map is reasonable for most purposes), but is a better design in the general case, in my opinion.

In a nutshell: if you want to reuse implementations, then expose "implementation modules", and define your "interface modules" on top of them.

Upvotes: 4

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66823

Seems to me a map is a (partial) function, which is a set of ordered pairs. If you define your comparison function correctly I think it can be done. You might have to add a function to the Set interface to account for the fact that two values can compare equal for purposes of membership but not actually be equal values. It doesn't seem possible to define the lookup function for the map with the current interface.

Upvotes: 3

Related Questions