Re: [Caml-list] Need help with higher order functors

[SEROT Jocelyn <Jocelyn.SEROT@univ-bpclermont.fr>]

Thanks a lot, Gabriel.

It works - although i must admit i don't really understand why :-S

Jocelyn

Gabriel Scherer <gabriel.scherer@gmail.com> a écrit :

> In your implementation, you can change
>     module R = Set.Make(P)
> into
>     module R = Set.Make(C(E1)(E2))
>
> Or simply use:
>
>     struct
>       module S1 = Set.Make (E1)
>       module S2 = Set.Make (E2)
>       include Set.Make(C(E1)(E2))
>
>       type t1 = S1.t
>       type t2 = S2.t
>
>       module P = C(E1)(E2)
>       let product s1 s2 =
>         let f x y t = add (P.product x y) t in
>         let g x t = S2.fold (f x) s2 t in
>         S1.fold g s1 empty
>     end
>
> On Fri, Jan 17, 2014 at 3:10 PM, SEROT Jocelyn
> <Jocelyn.SEROT@univ-bpclermont.fr> wrote:
>> Hi,
>>
>> I'm trying to implement an extension of the Set module including the notion
>> of cartesian product.
>>
>> The interface of the module is :
>>
>> (** File pset.mli *)
>>
>> module type ELT_PROD = sig
>>   include Set.OrderedType
>>   type t1
>>   type t2
>>   val product: t1 -> t2 -> t
>> end
>>
>> module type SET_PROD = sig
>>   include Set.S
>>   type t1
>>   type t2
>>   val product: t1 -> t2 -> t
>> end
>>
>> module MakeProduct
>>     (E1: Set.OrderedType)
>>     (E2: Set.OrderedType)
>>     (C: functor (E1: Set.OrderedType) -> functor (E2: Set.OrderedType) ->
>> ELT_PROD with type t1 = E1.t and type t2 = E2.t)
>>     : SET_PROD
>>       with type t1 = Set.Make(E1).t
>>       and type t2 = Set.Make(E2).t
>>       and type  t = Set.Make(C(E1)(E2)).t
>>       and type elt = C(E1)(E2).t
>>
>> The [MakeProduct] functor takes the signature of element types and a functor
>> describing how to combine these elements for building the set product.
>> An "obvious" definition of such a functor could be
>>
>> module MakePair (E1: Set.OrderedType) (E2: Set.OrderedType) = struct
>>   type t = E1.t * E2.t
>>   let compare = Pervasives.compare
>>   type t1 = E1.t
>>   type t2 = E2.t
>>   let product x y = x,y
>> end
>>
>> so that the definition of the "natural" cartesian product of two sets with
>> with elements having sig Int and Bool resp., should be
>>
>> module IntBoolSet = MakeProduct (Int) (Bool) (MakePair)
>>
>> but taking an extra functor argument for [MakeProduct] allows specialized
>> definitions of the product. For example, here's an alternative definition of
>> the MakePair functor which
>> could be passed to MakeProduct :
>>
>> module MakePair' (E1: Set.OrderedType) (E2: Set.OrderedType) = struct
>>   type t = Pair of E1.t * E2.t
>>   let compare = Pervasives.compare
>>   type t1 = E1.t
>>   type t2 = E2.t
>>   let product x y = Pair (x,y)
>> end
>>
>> The problem i have is in the implementation of the Mset module :
>>
>> (** File mset.ml *)
>>
>> module type SET_PROD = sig
>>   include Set.S
>>   type t1
>>   type t2
>>   val product: t1 -> t2 -> t
>> end
>>
>> module type ELT_PROD = sig
>>   include Set.OrderedType
>>   type t1
>>   type t2
>>   val product: t1 -> t2 -> t
>> end
>>
>> module MakeProduct
>>     (E1: Set.OrderedType)
>>     (E2: Set.OrderedType)
>>     (C: functor (E1: Set.OrderedType) -> functor (E2: Set.OrderedType) ->
>> ELT_PROD with type t1 = E1.t and type t2 = E2.t) =
>> struct
>>   module S1 = Set.Make (E1)
>>   module S2 = Set.Make (E2)
>>   module P = C (E1) (E2)
>>   module R = Set.Make(P)
>>   include R
>>   type t1 = S1.t
>>   type t2 = S2.t
>>   let product s1 s2 =
>>     let f x y t = R.add (P.product x y) t in
>>     let g x t = S2.fold (f x) s2 t in
>>     S1.fold g s1 R.empty
>> end
>>
>> Unfortunately, this does not compile. I get a long error message, ending
>> with :
>>
>> (* excerpt of the compiler log : *)
>>
>>            module R :
>>              sig
>>                type elt = P.t
>>                type t = Set.Make(P).t
>>                val empty : t
>>                ...
>>              end
>>            type elt = P.t
>>            type t = Set.Make(P).t
>>            val empty : t
>>            ....
>>            type t1 = S1.t
>>            type t2 = S2.t
>>            val product : S1.t -> S2.t -> R.t
>>          end
>>        is not included in
>>          sig
>>            type elt = C(E1)(E2).t
>>            type t = Set.Make(C(E1)(E2)).t
>>            val empty : t
>>            ...
>>            type t1 = Set.Make(E1).t
>>            type t2 = Set.Make(E2).t
>>            val product : t1 -> t2 -> t
>>          end
>>        Type declarations do not match:
>>          type t = Set.Make(P).t
>>        is not included in
>>          type t = Set.Make(C(E1)(E2)).t
>>
>> I suspect that some sharing constraint is missing here, but cannot spot
>> where.
>> I was expecting that  declaration
>>   module P = C (E1) (E2)
>> in the functor definition should automatically enforce the equality of types
>> P.t and C(E1)(E2).t, and, hence, of types Set.Make(P).t and
>> Set.Make(C(E1)(E2)).t.
>> Obviously not.
>>
>> Any help would be greatly appreciated ;)
>>
>> Thanks in advance,
>>
>> Jocelyn
>>
>>
>>
>>
>> --
>> Caml-list mailing list.  Subscription management and archives:
>> https://sympa.inria.fr/sympa/arc/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs