* [Caml-list] Need help with higher order functors
@ 2014-01-17 14:10 SEROT Jocelyn
2014-01-17 14:30 ` Gabriel Scherer
0 siblings, 1 reply; 3+ messages in thread
From: SEROT Jocelyn @ 2014-01-17 14:10 UTC (permalink / raw)
To: caml-list
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
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [Caml-list] Need help with higher order functors
2014-01-17 14:10 [Caml-list] Need help with higher order functors SEROT Jocelyn
@ 2014-01-17 14:30 ` Gabriel Scherer
2014-01-17 14:48 ` SEROT Jocelyn
0 siblings, 1 reply; 3+ messages in thread
From: Gabriel Scherer @ 2014-01-17 14:30 UTC (permalink / raw)
To: SEROT Jocelyn; +Cc: caml users
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
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [Caml-list] Need help with higher order functors
2014-01-17 14:30 ` Gabriel Scherer
@ 2014-01-17 14:48 ` SEROT Jocelyn
0 siblings, 0 replies; 3+ messages in thread
From: SEROT Jocelyn @ 2014-01-17 14:48 UTC (permalink / raw)
To: Gabriel Scherer; +Cc: caml users
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
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2014-01-17 14:48 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-01-17 14:10 [Caml-list] Need help with higher order functors SEROT Jocelyn
2014-01-17 14:30 ` Gabriel Scherer
2014-01-17 14:48 ` SEROT Jocelyn
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox