Functorized map: How to go from (polymorphic) map to set?

Functorized map: How to go from (polymorphic) map to set?

[Martin Percossi]

Hello, I'm a bit of a newbie to ocaml - I've programmed more in haskell 
plus all the other "standard" languages (C, java, ...). I'm testing 
ocaml by writing a little language of my own. Unfortunately, I'm 
somewhat stuck with something that I know in haskell would be quite easy 
to code using type classes. Here is a minimal example:

module type AbstractStringTable =
  sig
    type 'a table
    type 'a set
    (* Give me the set of entries, i.e. (string, value)
    pairs that are in the first table but not in the
    second, as a set *)
    val diff   : 'a table -> 'a table -> 'a set
  end;;
module StringTable : AbstractStringTable =
  struct
    module M = Map.Make(String)
    type 'a table = 'a M.t
    type 'a settype = string * 'a
    module IdTy : Set.OrderedType =
      struct
        type 'a t = 'a settype
        let compare (s1, _) (s2, _) = String.compare s1 s2
      end
    module S = Set.Make(IdTy)
    (* HERE'S THE PROBLEM! A SET WANTS A MONOMORPHIC TYPE!!!  *)
    type 'a set = 'a S.t
  end;;

And the compiler error I get is:
File "problem.ml", line 22, characters 6-112:
Signature mismatch:
Modules do not match:
  sig
    type 'a t = 'a settype
    val compare : String.t * 'a -> String.t * 'b -> int
  end
is not included in
  Set.OrderedType
Type declarations do not match:
  type 'a t = 'a settype
is not included in
  type t

So basically the compiler doesn't like me trying to make the Set.t type 
polymorphic, as it is in Map. Essentially, my intent is to have a table 
accessed by strings, pointing to anything == T. When I call 'diff', I 
would like to get Set of T. It's trivial to rewrite this in haskell 
(admittedly, using some extensions), like so:

module NoProblem where
import Data.Map as M
import Data.Set as S
type Table t = M.Map String t
type Entries t = S.Set (String, t)
class StringTable t where
  diff :: Table t -> Table t -> Entries t
instance Ord t => StringTable t where
  diff tl tr = let setOf t = S.fromList (M.assocs t) in
               setOf tl `S.difference` setOf tr

Is there a way I can accomplish the same thing in O'Caml?

Many thanks in advance,
Martin

Re: [Caml-list] Functorized map: How to go from (polymorphic) map to set?

[Martin Jambon]

On Sat, 28 Oct 2006, Martin Percossi wrote:

> Hello, I'm a bit of a newbie to ocaml - I've programmed more in haskell plus 
> all the other "standard" languages (C, java, ...). I'm testing ocaml by 
> writing a little language of my own. Unfortunately, I'm somewhat stuck with 
> something that I know in haskell would be quite easy to code using type 
> classes. Here is a minimal example:
>
> module type AbstractStringTable =
> sig
>   type 'a table
>   type 'a set
>   (* Give me the set of entries, i.e. (string, value)
>   pairs that are in the first table but not in the
>   second, as a set *)
>   val diff   : 'a table -> 'a table -> 'a set
> end;;
> module StringTable : AbstractStringTable =
> struct
>   module M = Map.Make(String)
>   type 'a table = 'a M.t
>   type 'a settype = string * 'a
>   module IdTy : Set.OrderedType =
>     struct
>       type 'a t = 'a settype
              ^^^^

The problem is here: "type t" is expected, not "type 'a t".

>       let compare (s1, _) (s2, _) = String.compare s1 s2
>     end
>   module S = Set.Make(IdTy)
>   (* HERE'S THE PROBLEM! A SET WANTS A MONOMORPHIC TYPE!!!  *)
>   type 'a set = 'a S.t
> end;;
>
> And the compiler error I get is:
> File "problem.ml", line 22, characters 6-112:
> Signature mismatch:
> Modules do not match:
> sig
>   type 'a t = 'a settype
>   val compare : String.t * 'a -> String.t * 'b -> int
> end
> is not included in
> Set.OrderedType
> Type declarations do not match:
> type 'a t = 'a settype
> is not included in
> type t
>
> So basically the compiler doesn't like me trying to make the Set.t type 
> polymorphic, as it is in Map.

If you look at the keys, in both cases they are monomorphic. So the 
solution here is to implement your StringTable module as a functor which 
takes the type of elements as argument.

Here's something that compiles:

module type AbstractStringTable =
sig
   type table
   type set
     (* Give me the set of entries, i.e. (string, value)
        pairs that are in the first table but not in the
        second, as a set *)
   val diff   : table -> table -> set
end;;

module type Elt_type =
sig
   type elt
end

module StringTable (E : Elt_type) : AbstractStringTable =
struct
   open E
   module M = Map.Make(String)
   type table = elt M.t
   type settype = string * elt
   module IdTy : Set.OrderedType =
      struct
        type t = settype
        let compare (s1, _) (s2, _) = String.compare s1 s2
      end
   module S = Set.Make(IdTy)
   (* HERE'S THE PROBLEM! A SET WANTS A MONOMORPHIC TYPE!!!  *)
   type set = S.t
   let diff = failwith "not implemented"
end;;



Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr

Re: [Caml-list] Functorized map: How to go from (polymorphic) map to set?

[Martin Percossi]

Thanks v. much for your help!

Martin Jambon wrote:
> On Sat, 28 Oct 2006, Martin Percossi wrote:
>
>> Hello, I'm a bit of a newbie to ocaml - I've programmed more in 
>> haskell plus all the other "standard" languages (C, java, ...). I'm 
>> testing ocaml by writing a little language of my own. Unfortunately, 
>> I'm somewhat stuck with something that I know in haskell would be 
>> quite easy to code using type classes. Here is a minimal example:
>>
>> module type AbstractStringTable =
>> sig
>>   type 'a table
>>   type 'a set
>>   (* Give me the set of entries, i.e. (string, value)
>>   pairs that are in the first table but not in the
>>   second, as a set *)
>>   val diff   : 'a table -> 'a table -> 'a set
>> end;;
>> module StringTable : AbstractStringTable =
>> struct
>>   module M = Map.Make(String)
>>   type 'a table = 'a M.t
>>   type 'a settype = string * 'a
>>   module IdTy : Set.OrderedType =
>>     struct
>>       type 'a t = 'a settype
>              ^^^^
>
> The problem is here: "type t" is expected, not "type 'a t".
>
>>       let compare (s1, _) (s2, _) = String.compare s1 s2
>>     end
>>   module S = Set.Make(IdTy)
>>   (* HERE'S THE PROBLEM! A SET WANTS A MONOMORPHIC TYPE!!!  *)
>>   type 'a set = 'a S.t
>> end;;
>>
>> And the compiler error I get is:
>> File "problem.ml", line 22, characters 6-112:
>> Signature mismatch:
>> Modules do not match:
>> sig
>>   type 'a t = 'a settype
>>   val compare : String.t * 'a -> String.t * 'b -> int
>> end
>> is not included in
>> Set.OrderedType
>> Type declarations do not match:
>> type 'a t = 'a settype
>> is not included in
>> type t
>>
>> So basically the compiler doesn't like me trying to make the Set.t 
>> type polymorphic, as it is in Map.
>
> If you look at the keys, in both cases they are monomorphic. So the 
> solution here is to implement your StringTable module as a functor 
> which takes the type of elements as argument.
>
> Here's something that compiles:
>
> module type AbstractStringTable =
> sig
>   type table
>   type set
>     (* Give me the set of entries, i.e. (string, value)
>        pairs that are in the first table but not in the
>        second, as a set *)
>   val diff   : table -> table -> set
> end;;
>
> module type Elt_type =
> sig
>   type elt
> end
>
> module StringTable (E : Elt_type) : AbstractStringTable =
> struct
>   open E
>   module M = Map.Make(String)
>   type table = elt M.t
>   type settype = string * elt
>   module IdTy : Set.OrderedType =
>      struct
>        type t = settype
>        let compare (s1, _) (s2, _) = String.compare s1 s2
>      end
>   module S = Set.Make(IdTy)
>   (* HERE'S THE PROBLEM! A SET WANTS A MONOMORPHIC TYPE!!!  *)
>   type set = S.t
>   let diff = failwith "not implemented"
> end;;
>
>
>
> Martin
>
> -- 
> Martin Jambon, PhD
> http://martin.jambon.free.fr
>