Making a polymorphic type non-polymorphic to comply with original signature

Making a polymorphic type non-polymorphic to comply with original signature

[Hugo Ferreira]

Hello,

I have the following definition:

module rec H :
   sig
       type 'a node =
           | Node of 'a node J.t
           | Leaf of 'a

      type 'a t = 'a node
      val equal : 'a t -> 'a t -> bool
     val hash : 'a t -> int
   end =
struct
     type 'a node =
         | Node of 'a node J.t
         | Leaf of 'a

     type 'a t = 'a node
     let equa = (==)
     let hash = Hashtbl.hash
end

and J : Hashtbl.S with type 'a key = 'a H.node = Hashtbl.Make( H )
;;

The data type 'a node is polymorphic. It is also a key used by the
hash-table. Note that H now does not comply with Hashtbl.HashedType
(because Hashtbl.HashedType is not polymorphic). By adding the
constraint "with type" also does not help.

Is it possible to make H comply with Hashtbl.HashedType i.e: make
J.Key = 'a H.node ?

TIA,
Hugo F.

Re: [Caml-list] Making a polymorphic type non-polymorphic to comply with original signature

[Daniel Bünzli]

Le 20 janv. 09 à 11:59, Hugo Ferreira a écrit :

> Is it possible to make H comply with Hashtbl.HashedType i.e: make
> J.Key = 'a H.node ?

This issue is well known (e.g. see here [1]). Your are running into  
limitations of the standard library. The only unsatisfying answer is  
to copy the code from the standard library and add the parameter  
yourself.

Best,

Daniel

[1] http://groups.google.com/group/fa.caml/browse_thread/thread/f2acb593da91553c?hl=fr&ie=UTF-8&q=type+var+in+functor+fa.caml

Re: [Caml-list] Making a polymorphic type non-polymorphic to comply with original signature

[David Teller]

It's probably feasible without copy & paste by building a functor on top
of the defunctorized hashtable in Batteries. Or by just using the
defunctorized hashtable of Batteries directly, although it's not as safe
as the functorized version, due to the absence of existential types.

Cheers,
 David

On Tue, 2009-01-20 at 12:24 +0100, Daniel Bünzli wrote:
> Le 20 janv. 09 à 11:59, Hugo Ferreira a écrit :
> 
> > Is it possible to make H comply with Hashtbl.HashedType i.e: make
> > J.Key = 'a H.node ?
> 
> This issue is well known (e.g. see here [1]). Your are running into  
> limitations of the standard library. The only unsatisfying answer is  
> to copy the code from the standard library and add the parameter  
> yourself.
> 
> Best,
> 
> Daniel
> 
> [1] http://groups.google.com/group/fa.caml/browse_thread/thread/f2acb593da91553c?hl=fr&ie=UTF-8&q=type+var+in+functor+fa.caml
> 
> ____________________________________________ugs
> 
-- 
David Teller-Rajchenbach
 Security of Distributed Systems
  http://www.univ-orleans.fr/lifo/Members/David.Teller
   Latest News of French Research: System being liquidated. Researchers angry. 

Re: [Caml-list] Making a polymorphic type non-polymorphic to comply with original signature

[Hugo Ferreira]

Hi Daniel,

Daniel Bünzli wrote:
> 
> Le 20 janv. 09 à 11:59, Hugo Ferreira a écrit :
> 
>> Is it possible to make H comply with Hashtbl.HashedType i.e: make
>> J.Key = 'a H.node ?
> 
> This issue is well known (e.g. see here [1]). Your are running into 
> limitations of the standard library. The only unsatisfying answer is to 
> copy the code from the standard library and add the parameter yourself.
> 

Thanks for the quick response. Back to the drawing board I guess.

Regards,
Hugo F.


> Best,
> 
> Daniel
> 
> [1] 
> http://groups.google.com/group/fa.caml/browse_thread/thread/f2acb593da91553c?hl=fr&ie=UTF-8&q=type+var+in+functor+fa.caml 
> 
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 

Re: [Caml-list] Making a polymorphic type non-polymorphic to comply with original signature

[Hugo Ferreira]

David Teller wrote:
> It's probably feasible without copy & paste by building a functor on top
> of the defunctorized hashtable in Batteries. Or by just using the
> defunctorized hashtable of Batteries directly, although it's not as safe
> as the functorized version, due to the absence of existential types.
> 

If I understand you correctly I would have to redefine equivalents for:
- HashedType
- S
- Make(H: HashedType)

Basically copy & paste these and change the type.
Doable although not to my liking.

TIA,
Hugo F.


> Cheers,
>  David
> 
> On Tue, 2009-01-20 at 12:24 +0100, Daniel Bünzli wrote:
>> Le 20 janv. 09 à 11:59, Hugo Ferreira a écrit :
>>
>>> Is it possible to make H comply with Hashtbl.HashedType i.e: make
>>> J.Key = 'a H.node ?
>> This issue is well known (e.g. see here [1]). Your are running into  
>> limitations of the standard library. The only unsatisfying answer is  
>> to copy the code from the standard library and add the parameter  
>> yourself.
>>
>> Best,
>>
>> Daniel
>>
>> [1] http://groups.google.com/group/fa.caml/browse_thread/thread/f2acb593da91553c?hl=fr&ie=UTF-8&q=type+var+in+functor+fa.caml
>>
>> ____________________________________________ugs
>>

Re: [Caml-list] Making a polymorphic type non-polymorphic to comply with original signature

[Thomas Gazagnaire]

[-- Attachment #1: Type: text/plain, Size: 2259 bytes --]

Or you can also functorize your own piece of code :

module Make (A : sig type t end) =
struct

    module rec H :
    sig
        type 'a node =
            | Node of 'a node J.t
            | Leaf of 'a

        type t = A.t node
        val equal : t -> t -> bool
        val hash : t -> int
    end =
    struct
        type 'a node =
            | Node of 'a node J.t
            | Leaf of 'a

        type t = A.t node
        let equal = (==)
        let hash = Hashtbl.hash
    end

    and J : Hashtbl.S with type key = A.t H.node = Hashtbl.Make( H )

end

2009/1/20 Hugo Ferreira <hmf@inescporto.pt>

> David Teller wrote:
>
>> It's probably feasible without copy & paste by building a functor on top
>> of the defunctorized hashtable in Batteries. Or by just using the
>> defunctorized hashtable of Batteries directly, although it's not as safe
>> as the functorized version, due to the absence of existential types.
>>
>>
> If I understand you correctly I would have to redefine equivalents for:
> - HashedType
> - S
> - Make(H: HashedType)
>
> Basically copy & paste these and change the type.
> Doable although not to my liking.
>
> TIA,
> Hugo F.
>
>
>  Cheers,
>>  David
>>
>> On Tue, 2009-01-20 at 12:24 +0100, Daniel Bünzli wrote:
>>
>>> Le 20 janv. 09 à 11:59, Hugo Ferreira a écrit :
>>>
>>>  Is it possible to make H comply with Hashtbl.HashedType i.e: make
>>>> J.Key = 'a H.node ?
>>>>
>>> This issue is well known (e.g. see here [1]). Your are running into
>>>  limitations of the standard library. The only unsatisfying answer is  to
>>> copy the code from the standard library and add the parameter  yourself.
>>>
>>> Best,
>>>
>>> Daniel
>>>
>>> [1]
>>> http://groups.google.com/group/fa.caml/browse_thread/thread/f2acb593da91553c?hl=fr&ie=UTF-8&q=type+var+in+functor+fa.caml
>>>
>>> ____________________________________________ugs
>>>
>>>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

[-- Attachment #2: Type: text/html, Size: 4543 bytes --]

Re: [Caml-list] Making a polymorphic type non-polymorphic to comply with original signature

[Hugo Ferreira]

Thomas Gazagnaire wrote:
> Or you can also functorize your own piece of code :
> 
> module Make (A : sig type t end) =
> struct
> 
>     module rec H :
>     sig
>         type 'a node =
>             | Node of 'a node J.t
>             | Leaf of 'a
>                  
>         type t = A.t node
>         val equal : t -> t -> bool
>         val hash : t -> int
>     end =
>     struct
>         type 'a node =
>             | Node of 'a node J.t
>             | Leaf of 'a
>                  
>         type t = A.t node
>         let equal = (==)
>         let hash = Hashtbl.hash
>     end
>        
>     and J : Hashtbl.S with type key = A.t H.node = Hashtbl.Make( H )
>    
> end
>

Incredible! You have just provided a excellent solution.
Works "out of the box":

# module N = Make(struct type t = int end ) ;;

# let jls = J.create 13 ;;
val jls : '_a N.J.t = <abstr>

# let r = H.Node(jls) ;;
val r : '_a N.H.node = N.H.Node <abstr>

# let _ = J.add jls r r ;;
- : unit = ()

# let x = J.find jls r ;;
val x : int N.H.node = N.H.Node <abstr>

# let r = (x == r ) ;;
val r : bool = true

Hmmm... now I wonder if that node type can also be pulled in by the
functor. If so we have a very general solution to the problem of
equality checking of polymorphic types. Anyone care to comment?

Once again Thomas,
thank you.
Hugo F.


> 2009/1/20 Hugo Ferreira <hmf@inescporto.pt <mailto:hmf@inescporto.pt>>
> 
>     David Teller wrote:
> 
>         It's probably feasible without copy & paste by building a
>         functor on top
>         of the defunctorized hashtable in Batteries. Or by just using the
>         defunctorized hashtable of Batteries directly, although it's not
>         as safe
>         as the functorized version, due to the absence of existential types.
> 
> 
>     If I understand you correctly I would have to redefine equivalents for:
>     - HashedType
>     - S
>     - Make(H: HashedType)
> 
>     Basically copy & paste these and change the type.
>     Doable although not to my liking.
> 
>     TIA,
>     Hugo F.
> 
> 
> 
>         Cheers,
>          David
> 
>         On Tue, 2009-01-20 at 12:24 +0100, Daniel Bünzli wrote:
> 
>             Le 20 janv. 09 à 11:59, Hugo Ferreira a écrit :
> 
>                 Is it possible to make H comply with Hashtbl.HashedType
>                 i.e: make
>                 J.Key = 'a H.node ?
> 
>             This issue is well known (e.g. see here [1]). Your are
>             running into  limitations of the standard library. The only
>             unsatisfying answer is  to copy the code from the standard
>             library and add the parameter  yourself.
> 
>             Best,
> 
>             Daniel
> 
>             [1]
>             http://groups.google.com/group/fa.caml/browse_thread/thread/f2acb593da91553c?hl=fr&ie=UTF-8&q=type+var+in+functor+fa.caml
>             <http://groups.google.com/group/fa.caml/browse_thread/thread/f2acb593da91553c?hl=fr&ie=UTF-8&q=type+var+in+functor+fa.caml>
> 
>             ____________________________________________ugs
> 
> 
>     _______________________________________________
>     Caml-list mailing list. Subscription management:
>     http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
>     Archives: http://caml.inria.fr
>     Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>     Bug reports: http://caml.inria.fr/bin/caml-bugs
> 
> 

Re: [Caml-list] Making a polymorphic type non-polymorphic to comply with original signature

[Martin Jambon]

Hugo Ferreira wrote:
> Hello,
> 
> I have the following definition:
> 
> module rec H :
>   sig
>       type 'a node =
>           | Node of 'a node J.t
>           | Leaf of 'a
> 
>      type 'a t = 'a node
>      val equal : 'a t -> 'a t -> bool
>     val hash : 'a t -> int
>   end =
> struct
>     type 'a node =
>         | Node of 'a node J.t
>         | Leaf of 'a
> 
>     type 'a t = 'a node
>     let equa = (==)
>     let hash = Hashtbl.hash
> end
> 
> and J : Hashtbl.S with type 'a key = 'a H.node = Hashtbl.Make( H )
> ;;
> 
> The data type 'a node is polymorphic. It is also a key used by the
> hash-table. Note that H now does not comply with Hashtbl.HashedType
> (because Hashtbl.HashedType is not polymorphic). By adding the
> constraint "with type" also does not help.
> 
> Is it possible to make H comply with Hashtbl.HashedType i.e: make
> J.Key = 'a H.node ?


I just posted an implementation of polymorphic hash tables with physical
comparison, using the Obj module:

  http://martin.jambon.free.fr/phys.html

It is the following code:

(***** phys.mli *****)

type ('a, 'b) t

val add : ('a, 'b) t -> 'a -> 'b -> unit
val clear : ('a, 'b) t -> unit
val copy : ('a, 'b) t -> ('a, 'b) t
val create : int -> ('a, 'b) t
val find : ('a, 'b) t -> 'a -> 'b
val find_all : ('a, 'b) t -> 'a -> 'b list
val fold : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c
val iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit
val length : ('a, 'b) t -> int
val mem : ('a, 'b) t -> 'a -> bool
val remove : ('a, 'b) t -> 'a -> unit
val replace : ('a, 'b) t -> 'a -> 'b -> unit



(***** phys.ml *****)

(*
  This implementation uses the Obj module which allows to transgress
  the type system. It is not regular OCaml.
*)

module Magic_key =
struct
  type t = Obj.t
  let equal = ( == )
  let hash = Hashtbl.hash
end

module Magic_table = Hashtbl.Make (Magic_key)


type ('a, 'b) t = 'b Magic_table.t

let add tbl k v = Magic_table.add tbl (Obj.repr k) v
let clear tbl = Magic_table.clear tbl
let copy tbl = Magic_table.copy tbl
let create n = Magic_table.create n
let find tbl k = Magic_table.find tbl (Obj.repr k)
let find_all tbl k = Magic_table.find_all tbl (Obj.repr k)
let fold f tbl accu = Magic_table.fold (Obj.magic f) (Obj.magic tbl) accu
let iter f tbl = Magic_table.iter (Obj.magic f) (Obj.magic tbl)
let length tbl = Magic_table.length tbl
let mem tbl k = Magic_table.mem tbl (Obj.repr k)
let remove tbl k = Magic_table.remove tbl (Obj.repr k)
let replace tbl k v = Magic_table.replace tbl (Obj.repr k) v


(*****************)



Martin

-- 
http://mjambon.com/

Re: [Caml-list] Making a polymorphic type non-polymorphic to comply with original signature

[Hugo Ferreira]

Martin,

Thanks for the alternate solution. It seems
to provide a much simpler interface i.e:
doesn't require such a convoluted way of
declaring the types.

I wonder if it has any run-time benefits
compared to the previous solution.

Regards,
Hugo F.



Martin Jambon wrote:
> Hugo Ferreira wrote:
>> Hello,
>>
>> I have the following definition:
>>
>> module rec H :
>>   sig
>>       type 'a node =
>>           | Node of 'a node J.t
>>           | Leaf of 'a
>>
>>      type 'a t = 'a node
>>      val equal : 'a t -> 'a t -> bool
>>     val hash : 'a t -> int
>>   end =
>> struct
>>     type 'a node =
>>         | Node of 'a node J.t
>>         | Leaf of 'a
>>
>>     type 'a t = 'a node
>>     let equa = (==)
>>     let hash = Hashtbl.hash
>> end
>>
>> and J : Hashtbl.S with type 'a key = 'a H.node = Hashtbl.Make( H )
>> ;;
>>
>> The data type 'a node is polymorphic. It is also a key used by the
>> hash-table. Note that H now does not comply with Hashtbl.HashedType
>> (because Hashtbl.HashedType is not polymorphic). By adding the
>> constraint "with type" also does not help.
>>
>> Is it possible to make H comply with Hashtbl.HashedType i.e: make
>> J.Key = 'a H.node ?
> 
> 
> I just posted an implementation of polymorphic hash tables with physical
> comparison, using the Obj module:
> 
>   http://martin.jambon.free.fr/phys.html
> 
> It is the following code:
> 
> (***** phys.mli *****)
> 
> type ('a, 'b) t
> 
> val add : ('a, 'b) t -> 'a -> 'b -> unit
> val clear : ('a, 'b) t -> unit
> val copy : ('a, 'b) t -> ('a, 'b) t
> val create : int -> ('a, 'b) t
> val find : ('a, 'b) t -> 'a -> 'b
> val find_all : ('a, 'b) t -> 'a -> 'b list
> val fold : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c
> val iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit
> val length : ('a, 'b) t -> int
> val mem : ('a, 'b) t -> 'a -> bool
> val remove : ('a, 'b) t -> 'a -> unit
> val replace : ('a, 'b) t -> 'a -> 'b -> unit
> 
> 
> 
> (***** phys.ml *****)
> 
> (*
>   This implementation uses the Obj module which allows to transgress
>   the type system. It is not regular OCaml.
> *)
> 
> module Magic_key =
> struct
>   type t = Obj.t
>   let equal = ( == )
>   let hash = Hashtbl.hash
> end
> 
> module Magic_table = Hashtbl.Make (Magic_key)
> 
> 
> type ('a, 'b) t = 'b Magic_table.t
> 
> let add tbl k v = Magic_table.add tbl (Obj.repr k) v
> let clear tbl = Magic_table.clear tbl
> let copy tbl = Magic_table.copy tbl
> let create n = Magic_table.create n
> let find tbl k = Magic_table.find tbl (Obj.repr k)
> let find_all tbl k = Magic_table.find_all tbl (Obj.repr k)
> let fold f tbl accu = Magic_table.fold (Obj.magic f) (Obj.magic tbl) accu
> let iter f tbl = Magic_table.iter (Obj.magic f) (Obj.magic tbl)
> let length tbl = Magic_table.length tbl
> let mem tbl k = Magic_table.mem tbl (Obj.repr k)
> let remove tbl k = Magic_table.remove tbl (Obj.repr k)
> let replace tbl k v = Magic_table.replace tbl (Obj.repr k) v
> 
> 
> (*****************)
> 
> 
> 
> Martin
>