polymorphic lists, existential types and asorted other hattery

polymorphic lists, existential types and asorted other hattery

[Peng Zang]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi,

Is there a way to create lists in which the elements may be of
differing types but which all have some set of operations defined
(eg. tostr) in common?  One can then imagine mapping over such lists
with "generic" versions of those common operations.  Here's a concrete
example of what I mean:

  module Int = struct
    type t = int
    let show x = string_of_int x
  end
  module Float = struct
    type t = float
    let show x = string_of_float x
  end
  module Bool = struct
    type t = bool
    let show x = string_of_bool x
  end

  let xs = [`Int 1; `Float 2.0; `Bool false]
  let showany x = match x with
    | `Int x -> Int.show x
    | `Float x -> Float.show x
    | `Bool x -> Bool.show x
  ;;
  List.map showany xs;;

Essentially we have ints, floats and bools.  All these types can be
shown.  It would be nice to be able to create a list of them [1; 2.0;
false] that you can then map a generalized show over.  In the above
example, I used polymorphic variants in order to get them into the
same list and then had to define my own generalized show function,
"showany".  This is fine as there is only one shared operation but if
there is a large set of these common operations, it becomes
impractical to define a generalized version for each of them.

I've come across a way to do this in haskell using what they call
"existential types".

  http://www.haskell.org/haskellwiki/Existential_type

I don't really understand existential types however and don't know if
OCaml has them nor how to use them.

So.  How can one do this in OCaml?  Is there perhaps a camlp4
extension that can do this?  Is there a possible functor trick that
can take N modules as arguments and spit out a new module with a
generalized type that can take on any of the types in the arguments
and also make generalized versions of operations common to the N
modules?  Are there existential types or equivalents in OCaml?  If so
how does one go about using them?

Thanks in advance to anyone who forays into this bundle of questions.

Peng
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFHOd52fIRcEFL/JewRAkZNAJ9MUE4Ph4ybbtKjiV9h9ZxPsvDwGQCgwIJz
aOceerrixiPZosJq4a+r0qM=
=zOZF
-----END PGP SIGNATURE-----

Re: [Caml-list] polymorphic lists, existential types and asorted other hattery

[Arnaud Spiwack]

What you are describing is rather existential in essence. Existential 
type do not exist in OCaml but are encodable through interesting tricks 
(I know so because I kinda asked a similar question a few month ago :p 
). See discussion thread here (which was pointed to me this very time I 
asked the question) : http://tinyurl.com/2p5oan .

Here is your example refactored with this methodology :

type 'e show = { item : 'e; show: 'e-> string }
type 't show_scope = { bind_show : 'e. 'e show -> 't }
type showable = { open_showable : 't. 't show_scope -> 't }

let create_showable sh it =
  { open_showable = fun scope -> scope.bind_show { item = it ; show = sh } }

let use_showable shw f = shw.open_showable f

let show shw = use_showable shw { bind_show = fun sh -> sh.show sh.item }

let showable_int = create_showable string_of_int
let showable_bool = create_showable string_of_bool
let showable_float = create_showable string_of_float

let xs = [(showable_int 1); (showable_float 2.0); (showable_bool false)]

List.map show xs

Peng Zang a écrit :
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Hi,
>
> Is there a way to create lists in which the elements may be of
> differing types but which all have some set of operations defined
> (eg. tostr) in common?  One can then imagine mapping over such lists
> with "generic" versions of those common operations.  Here's a concrete
> example of what I mean:
>
>   module Int = struct
>     type t = int
>     let show x = string_of_int x
>   end
>   module Float = struct
>     type t = float
>     let show x = string_of_float x
>   end
>   module Bool = struct
>     type t = bool
>     let show x = string_of_bool x
>   end
>
>   let xs = [`Int 1; `Float 2.0; `Bool false]
>   let showany x = match x with
>     | `Int x -> Int.show x
>     | `Float x -> Float.show x
>     | `Bool x -> Bool.show x
>   ;;
>   List.map showany xs;;
>
> Essentially we have ints, floats and bools.  All these types can be
> shown.  It would be nice to be able to create a list of them [1; 2.0;
> false] that you can then map a generalized show over.  In the above
> example, I used polymorphic variants in order to get them into the
> same list and then had to define my own generalized show function,
> "showany".  This is fine as there is only one shared operation but if
> there is a large set of these common operations, it becomes
> impractical to define a generalized version for each of them.
>
> I've come across a way to do this in haskell using what they call
> "existential types".
>
>   http://www.haskell.org/haskellwiki/Existential_type
>
> I don't really understand existential types however and don't know if
> OCaml has them nor how to use them.
>
> So.  How can one do this in OCaml?  Is there perhaps a camlp4
> extension that can do this?  Is there a possible functor trick that
> can take N modules as arguments and spit out a new module with a
> generalized type that can take on any of the types in the arguments
> and also make generalized versions of operations common to the N
> modules?  Are there existential types or equivalents in OCaml?  If so
> how does one go about using them?
>
> Thanks in advance to anyone who forays into this bundle of questions.
>
> Peng
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v2.0.7 (GNU/Linux)
>
> iD8DBQFHOd52fIRcEFL/JewRAkZNAJ9MUE4Ph4ybbtKjiV9h9ZxPsvDwGQCgwIJz
> aOceerrixiPZosJq4a+r0qM=
> =zOZF
> -----END PGP SIGNATURE-----
>
> _______________________________________________
> 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] polymorphic lists, existential types and asorted other hattery

[Peng Zang]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Ahh, right!  Sorry, I forgot to mention I'm looking for a possible solution 
without classes.

I ask because most of my code base is modules and functor based and it would 
be a pain to convert over.  Also because performance is typically better with 
just functions and data types.

I feel like a solution without the OO side is possible through perhaps an 
analog of existential types?

Peng

On Tuesday 13 November 2007 04:14:06 pm Dmitri Boulytchev wrote:
>     Try using classes for this purpose:
>
> let show l = List.map (fun x -> x#show) l
>
> class integer x =
>   object
>     method show = string_of_int x
>   end
>
> class floating x =
>   object
>     method show = string_of_float x
>   end
>
> class boolean x =
>   object
>     method show = string_of_bool x
>   end
>
>
> let _ =
>   List.iter
>     (Printf.printf "%s\n")
>     (show
>        [
>      new integer 10;
>          new floating 3.14;
>          new boolean true;
>        ]
>     )
>
>     Best regards,
>     Dmitri Boulytchev,
>     St.Petersburg State University.
>
> > Hi,
> >
> > Is there a way to create lists in which the elements may be of
> > differing types but which all have some set of operations defined
> > (eg. tostr) in common?  One can then imagine mapping over such lists
> > with "generic" versions of those common operations.  Here's a concrete
> > example of what I mean:
> >
> >   module Int = struct
> >     type t = int
> >     let show x = string_of_int x
> >   end
> >   module Float = struct
> >     type t = float
> >     let show x = string_of_float x
> >   end
> >   module Bool = struct
> >     type t = bool
> >     let show x = string_of_bool x
> >   end
> >
> >   let xs = [`Int 1; `Float 2.0; `Bool false]
> >   let showany x = match x with
> >
> >     | `Int x -> Int.show x
> >     | `Float x -> Float.show x
> >     | `Bool x -> Bool.show x
> >
> >   ;;
> >   List.map showany xs;;
> >
> > Essentially we have ints, floats and bools.  All these types can be
> > shown.  It would be nice to be able to create a list of them [1; 2.0;
> > false] that you can then map a generalized show over.  In the above
> > example, I used polymorphic variants in order to get them into the
> > same list and then had to define my own generalized show function,
> > "showany".  This is fine as there is only one shared operation but if
> > there is a large set of these common operations, it becomes
> > impractical to define a generalized version for each of them.
> >
> > I've come across a way to do this in haskell using what they call
> > "existential types".
> >
> >   http://www.haskell.org/haskellwiki/Existential_type
> >
> > I don't really understand existential types however and don't know if
> > OCaml has them nor how to use them.
> >
> > So.  How can one do this in OCaml?  Is there perhaps a camlp4
> > extension that can do this?  Is there a possible functor trick that
> > can take N modules as arguments and spit out a new module with a
> > generalized type that can take on any of the types in the arguments
> > and also make generalized versions of operations common to the N
> > modules?  Are there existential types or equivalents in OCaml?  If so
> > how does one go about using them?
> >
> > Thanks in advance to anyone who forays into this bundle of questions.
> >
> > Peng
>
> _______________________________________________
> 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


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFHOev1fIRcEFL/JewRAsbpAKCn2Kn/1eKHNVsukHU8IJvcJFcYdACgsgpr
Ln3sZuR+I1aA+yl++iZxsLc=
=2TsY
-----END PGP SIGNATURE-----

Re: [Caml-list] polymorphic lists, existential types and asorted other hattery

[Julien Moutinho]

On Tue, Nov 13, 2007 at 12:27:07PM -0500, Peng Zang wrote:
> Is there a way to create lists in which the elements may be of
> differing types but which all have some set of operations defined
> (eg. tostr) in common?
> [...]

Objects may be of interest to you:

% cat file.ml
class ['e] skel (e: 'e) =
  object
    val mutable e = e
    method get = e
    method set x = e <- x
  end

class virtual ['e] xs
  (to_string: 'e -> string) =
  object (self)
    method virtual get : 'e
    method coerce = (self :> < show : string >)
    method show = to_string self#get
  end

class oint (e: 'e) =
  object
    inherit ['e] skel e
    inherit ['e] xs string_of_int
  end
class ofloat (e: 'e) =
  object
    inherit ['e] skel e
    inherit ['e] xs string_of_float
  end

let xs =
  [ (new oint 1)#coerce
  ; (new ofloat 2.0)#coerce
  ; (new oint 3 :> < show : string >)
  ; (object method show = "soleil" end)
  ]
;;

List.iter (fun o -> print_endline o#show) xs

% ocaml file.ml
1
2.
3
soleil

% ocamlc -i file.ml
class ['a] skel :
  'a -> object val mutable e : 'a method get : 'a method set : 'a -> unit end
class virtual ['a] xs :
  ('a -> string) ->
  object
    method coerce : < show : string >
    method virtual get : 'a
    method show : string
  end
class oint :
  int ->
  object
    val mutable e : int
    method coerce : < show : string >
    method get : int
    method set : int -> unit
    method show : string
  end
class ofloat :
  float ->
  object
    val mutable e : float
    method coerce : < show : string >
    method get : float
    method set : float -> unit
    method show : string
  end
val xs : < show : string > list

HTH,
  Julien.

Re: [Caml-list] polymorphic lists, existential types and asorted other hattery

[Julien Moutinho]

On Tue, 13 Nov 2007 13:24:51 -0500, Peng Zang wrote:
> Ahh, right!  Sorry, I forgot to mention I'm looking for a possible solution
> without classes.
Arf.

Re: [Caml-list] polymorphic lists, existential types and asorted other hattery

[Benjamin Canou]

  Hi,

I've simulated objects with records like this in the past in when I
didn't need method resolution, and this thread made me worry about the
execution speed of such a pattern compared to ocaml objects.
So I made a little comparison between records and classes to do this
task (the code follows my message). Here is the result :

benjamin@benjamin-laptop:~/Work/Stuff$ ocamlopt classesvsrecords.ml -o
classesvsrecords && ./classesvsrecords
Classes: build = 1.316082, apply = 2.324145
Records: build = 1.872116, apply = 2.320145

Basically, objects are created faster than records (I think that an
object is created in O(1) whereas a record takes O(number of closures)
to be filled). Calls take the same time.

So, if you have to allocate a great number of values, then I think you
should consider using objects, otherwise, records wrapping the values
seem to be a correct option.

  Benjamin.

(* classes *)

let show l = List.map (fun x -> x#show) l

class integer x =
  object
    method show = print_int x
    method to_string = string_of_int x
  end

class floating x =
  object
    method show = print_float x
    method to_string = string_of_float x
  end
    
(* records *)

type element = { show : unit -> unit ; to_string : unit -> string }

let wrap_int x = {
  show = (fun () -> print_int x) ; 
  to_string = (fun () -> string_of_int x)
}

let wrap_float x = {
  show = (fun () -> print_float x) ;
  to_string = (fun () -> string_of_float x)
}
  
(* bench *)

let test_classes () =
  let rec build_classes n acc =
    if n <= 0 then
      acc
    else
      build_classes
	(pred n)
	((new floating (float_of_int n))
	 :: (new integer n)
	 :: acc)
  in
  let t1 = Sys.time () in
  let list = build_classes 1000000 [] in
  let t2 = Sys.time () in
    List.iter (fun x -> ignore (x#to_string)) list ;
    t2 -. t1, Sys.time () -. t2

let test_records () =
  let rec build_records n acc =
    if n <= 0 then
      acc
    else
      build_records
	(pred n)
	((wrap_float (float_of_int n))
	 :: (wrap_int n)
	 :: acc)
  in
  let t1 = Sys.time () in
  let list = build_records 1000000 [] in
  let t2 = Sys.time () in
    List.iter (fun x -> ignore (x.to_string ())) list ;
    t2 -. t1, Sys.time () -. t2

let _ =
  let tci, tca = test_classes ()
  and tri, tra = test_records () in
  Printf.printf
    "Classes: build = %f, apply = %f\nRecords: build = %f, apply = %f
\n" 
    tci tca tri tra


Le mardi 13 novembre 2007 à 21:39 +0000, Dmitri Boulytchev a écrit :
> Are structures allowed? :)
> 
> type t = {show : unit -> string}
> 
> let show l = List.map (fun x -> x.show ()) l
> 
> let integer  x = {show = fun () -> string_of_int   x}
> let floating x = {show = fun () -> string_of_float x}
> let boolean  x = {show = fun () -> string_of_bool  x}
> 
> let _ =
>   List.iter
>     (Printf.printf "%s\n")
>     (show
>        [
>      integer 10;
>          floating 3.14;
>          boolean true;
>        ]
>     )
> 
>     OCaml does not have Haskell-style existential types (I don't exactly
> know why, but can
> presume that they may interfere with objects, which  considered to be
> much more worthy).
>      I like modules and functors very much, too, but, first, modules are
> not "first-class
> citizens", and second, there may be no need to re-implement all your
> stuff to
> start using objects --- OCaml is fairy orthogonal language.
> 
>     Best regards,
>     DB.
> 
>     P.S. Objects are efficient :)
>    
> 
> 
> > Ahh, right!  Sorry, I forgot to mention I'm looking for a possible
> > solution
> > without classes.
> >
> > I ask because most of my code base is modules and functor based and it
> > would
> > be a pain to convert over.  Also because performance is typically
> > better with
> > just functions and data types.
> >
> > I feel like a solution without the OO side is possible through perhaps an
> > analog of existential types?
> >
> > Peng
> >
> > On Tuesday 13 November 2007 04:14:06 pm Dmitri Boulytchev wrote:
> >
> > >    Try using classes for this purpose:
> >
> > >let show l = List.map (fun x -> x#show) l
> >
> > >class integer x =
> > >  object
> > >    method show = string_of_int x
> > >  end
> >
> > >class floating x =
> > >  object
> > >    method show = string_of_float x
> > >  end
> >
> > >class boolean x =
> > >  object
> > >    method show = string_of_bool x
> > >  end
> >
> >
> > >let _ =
> > >  List.iter
> > >    (Printf.printf "%s\n")
> > >    (show
> > >       [
> > >     new integer 10;
> > >         new floating 3.14;
> > >         new boolean true;
> > >       ]
> > >    )
> >
> > >    Best regards,
> > >    Dmitri Boulytchev,
> > >    St.Petersburg State University.
> >
> > >>Hi,
> > >>
> > >>Is there a way to create lists in which the elements may be of
> > >>differing types but which all have some set of operations defined
> > >>(eg. tostr) in common?  One can then imagine mapping over such lists
> > >>with "generic" versions of those common operations.  Here's a concrete
> > >>example of what I mean:
> > >>
> > >>  module Int = struct
> > >>    type t = int
> > >>    let show x = string_of_int x
> > >>  end
> > >>  module Float = struct
> > >>    type t = float
> > >>    let show x = string_of_float x
> > >>  end
> > >>  module Bool = struct
> > >>    type t = bool
> > >>    let show x = string_of_bool x
> > >>  end
> > >>
> > >>  let xs = [`Int 1; `Float 2.0; `Bool false]
> > >>  let showany x = match x with
> > >>
> > >>    | `Int x -> Int.show x
> > >>    | `Float x -> Float.show x
> > >>    | `Bool x -> Bool.show x
> > >>
> > >>  ;;
> > >>  List.map showany xs;;
> > >>
> > >>Essentially we have ints, floats and bools.  All these types can be
> > >>shown.  It would be nice to be able to create a list of them [1; 2.0;
> > >>false] that you can then map a generalized show over.  In the above
> > >>example, I used polymorphic variants in order to get them into the
> > >>same list and then had to define my own generalized show function,
> > >>"showany".  This is fine as there is only one shared operation but if
> > >>there is a large set of these common operations, it becomes
> > >>impractical to define a generalized version for each of them.
> > >>
> > >>I've come across a way to do this in haskell using what they call
> > >>"existential types".
> > >>
> > >>  http://www.haskell.org/haskellwiki/Existential_type
> > >>
> > >>I don't really understand existential types however and don't know if
> > >>OCaml has them nor how to use them.
> > >>
> > >>So.  How can one do this in OCaml?  Is there perhaps a camlp4
> > >>extension that can do this?  Is there a possible functor trick that
> > >>can take N modules as arguments and spit out a new module with a
> > >>generalized type that can take on any of the types in the arguments
> > >>and also make generalized versions of operations common to the N
> > >>modules?  Are there existential types or equivalents in OCaml?  If so
> > >>how does one go about using them?
> > >>
> > >>Thanks in advance to anyone who forays into this bundle of questions.
> > >>
> > >>Peng
> >
> > >_______________________________________________
> > >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
> >
> >
> >
> 
> _______________________________________________
> 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
> 
> 
> _______________________________________________
> 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] polymorphic lists, existential types and asorted other hattery

[Dmitri Boulytchev]

    Try using classes for this purpose:

let show l = List.map (fun x -> x#show) l

class integer x =
  object
    method show = string_of_int x
  end

class floating x =
  object
    method show = string_of_float x
  end

class boolean x =
  object
    method show = string_of_bool x
  end


let _ =
  List.iter
    (Printf.printf "%s\n")
    (show
       [
     new integer 10;
         new floating 3.14;
         new boolean true;
       ]
    )

    Best regards,
    Dmitri Boulytchev,
    St.Petersburg State University.

> Hi,
>
> Is there a way to create lists in which the elements may be of
> differing types but which all have some set of operations defined
> (eg. tostr) in common?  One can then imagine mapping over such lists
> with "generic" versions of those common operations.  Here's a concrete
> example of what I mean:
>
>   module Int = struct
>     type t = int
>     let show x = string_of_int x
>   end
>   module Float = struct
>     type t = float
>     let show x = string_of_float x
>   end
>   module Bool = struct
>     type t = bool
>     let show x = string_of_bool x
>   end
>
>   let xs = [`Int 1; `Float 2.0; `Bool false]
>   let showany x = match x with
>     | `Int x -> Int.show x
>     | `Float x -> Float.show x
>     | `Bool x -> Bool.show x
>   ;;
>   List.map showany xs;;
>
> Essentially we have ints, floats and bools.  All these types can be
> shown.  It would be nice to be able to create a list of them [1; 2.0;
> false] that you can then map a generalized show over.  In the above
> example, I used polymorphic variants in order to get them into the
> same list and then had to define my own generalized show function,
> "showany".  This is fine as there is only one shared operation but if
> there is a large set of these common operations, it becomes
> impractical to define a generalized version for each of them.
>
> I've come across a way to do this in haskell using what they call
> "existential types".
>
>   http://www.haskell.org/haskellwiki/Existential_type
>
> I don't really understand existential types however and don't know if
> OCaml has them nor how to use them.
>
> So.  How can one do this in OCaml?  Is there perhaps a camlp4
> extension that can do this?  Is there a possible functor trick that
> can take N modules as arguments and spit out a new module with a
> generalized type that can take on any of the types in the arguments
> and also make generalized versions of operations common to the N
> modules?  Are there existential types or equivalents in OCaml?  If so
> how does one go about using them?
>
> Thanks in advance to anyone who forays into this bundle of questions.
>
> Peng


_______________________________________________
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] polymorphic lists, existential types and asorted other hattery

[Dmitri Boulytchev]

    Are structures allowed? :)

type t = {show : unit -> string}

let show l = List.map (fun x -> x.show ()) l

let integer  x = {show = fun () -> string_of_int   x}
let floating x = {show = fun () -> string_of_float x}
let boolean  x = {show = fun () -> string_of_bool  x}

let _ =
  List.iter
    (Printf.printf "%s\n")
    (show
       [
     integer 10;
         floating 3.14;
         boolean true;
       ]
    )

    OCaml does not have Haskell-style existential types (I don't exactly
know why, but can
presume that they may interfere with objects, which  considered to be
much more worthy).
     I like modules and functors very much, too, but, first, modules are
not "first-class
citizens", and second, there may be no need to re-implement all your
stuff to
start using objects --- OCaml is fairy orthogonal language.

    Best regards,
    DB.

    P.S. Objects are efficient :)
   


> Ahh, right!  Sorry, I forgot to mention I'm looking for a possible
> solution
> without classes.
>
> I ask because most of my code base is modules and functor based and it
> would
> be a pain to convert over.  Also because performance is typically
> better with
> just functions and data types.
>
> I feel like a solution without the OO side is possible through perhaps an
> analog of existential types?
>
> Peng
>
> On Tuesday 13 November 2007 04:14:06 pm Dmitri Boulytchev wrote:
>
> >    Try using classes for this purpose:
>
> >let show l = List.map (fun x -> x#show) l
>
> >class integer x =
> >  object
> >    method show = string_of_int x
> >  end
>
> >class floating x =
> >  object
> >    method show = string_of_float x
> >  end
>
> >class boolean x =
> >  object
> >    method show = string_of_bool x
> >  end
>
>
> >let _ =
> >  List.iter
> >    (Printf.printf "%s\n")
> >    (show
> >       [
> >     new integer 10;
> >         new floating 3.14;
> >         new boolean true;
> >       ]
> >    )
>
> >    Best regards,
> >    Dmitri Boulytchev,
> >    St.Petersburg State University.
>
> >>Hi,
> >>
> >>Is there a way to create lists in which the elements may be of
> >>differing types but which all have some set of operations defined
> >>(eg. tostr) in common?  One can then imagine mapping over such lists
> >>with "generic" versions of those common operations.  Here's a concrete
> >>example of what I mean:
> >>
> >>  module Int = struct
> >>    type t = int
> >>    let show x = string_of_int x
> >>  end
> >>  module Float = struct
> >>    type t = float
> >>    let show x = string_of_float x
> >>  end
> >>  module Bool = struct
> >>    type t = bool
> >>    let show x = string_of_bool x
> >>  end
> >>
> >>  let xs = [`Int 1; `Float 2.0; `Bool false]
> >>  let showany x = match x with
> >>
> >>    | `Int x -> Int.show x
> >>    | `Float x -> Float.show x
> >>    | `Bool x -> Bool.show x
> >>
> >>  ;;
> >>  List.map showany xs;;
> >>
> >>Essentially we have ints, floats and bools.  All these types can be
> >>shown.  It would be nice to be able to create a list of them [1; 2.0;
> >>false] that you can then map a generalized show over.  In the above
> >>example, I used polymorphic variants in order to get them into the
> >>same list and then had to define my own generalized show function,
> >>"showany".  This is fine as there is only one shared operation but if
> >>there is a large set of these common operations, it becomes
> >>impractical to define a generalized version for each of them.
> >>
> >>I've come across a way to do this in haskell using what they call
> >>"existential types".
> >>
> >>  http://www.haskell.org/haskellwiki/Existential_type
> >>
> >>I don't really understand existential types however and don't know if
> >>OCaml has them nor how to use them.
> >>
> >>So.  How can one do this in OCaml?  Is there perhaps a camlp4
> >>extension that can do this?  Is there a possible functor trick that
> >>can take N modules as arguments and spit out a new module with a
> >>generalized type that can take on any of the types in the arguments
> >>and also make generalized versions of operations common to the N
> >>modules?  Are there existential types or equivalents in OCaml?  If so
> >>how does one go about using them?
> >>
> >>Thanks in advance to anyone who forays into this bundle of questions.
> >>
> >>Peng
>
> >_______________________________________________
> >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
>
>
>

_______________________________________________
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] polymorphic lists, existential types and asorted other hattery

[Jacques Garrigue]

From: Peng Zang <peng.zang@gmail.com>

> I've come across a way to do this in haskell using what they call
> "existential types".
> 
>   http://www.haskell.org/haskellwiki/Existential_type
> 
> I don't really understand existential types however and don't know if
> OCaml has them nor how to use them.

Notwithstanding your reluctance to use them, objects in ocaml are
really what amounts to Haskell's existential types, particularly
those for which a type class is specified. Put the other way round,
most examples of constrained existential types (i.e. where there is a
type class specifiying the existential) are just encodings for
objects. The encoding of objects through existentials has been known
for a long time. OCaml doesn't need this encoding because it has
primitive objects.

>From an implementation point of view, constrained existentials need to
be accompanied by their dictionaries, which is exactly the same thing
as the method table in an object, so even the implementation is very
similar.

Method calls on arbitrary objects can be slow. This is because, due to
subtyping, in some situations there is no way to know where the method
will be in the table, and a binary search has to be done. However,
this overhead can be avoided if all objects used in a specific method
call have the same methods. That is, they should have the same
interface, without using subtyping. That way, the method will be at
the same position in all objects, and this position is cached (for
native code).
(Note that this also means that any benchmark on the performance of
objects shall consider the impact of cacheing, which can be hard to
evaluate in micro-benchmarks.)

Dmitri's example had this property, so it should display good
performance (as good as explicit existential encodings.)

Jacques Garrigue

Re: [Caml-list] polymorphic lists, existential types and asorted other hattery

[Peng Zang]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Wow, alright.  First I want to thank everyone for replying to my post.  You 
guys have been extremely helpful and I have definitely gained a better 
understanding of this issue.

Jacques, your explanation of how existential types are really just a way of 
encoding objects helps me understand both a lot better.  I never understood 
the connection before.  I also appreciate your tip on speeding up method 
calls.

Arnaud, your trick for encoding existencial types is fascinating.  I haven't 
followed through your reference thread through yet, but I'm sure I'll be 
doing that later today.

Dmitri and Benjamin, the OO examples and benchmarking makes it clear to me 
that objects can be quite fast.  I don't know where I read about objects 
being slow but that's clearly not the case here.


Overall I think the OO solution is what I am looking for.  I had been under 
the impression that OO was slower and that it was some thing unpleasant from 
various readings (eg. Yaron Minsky's summary  
http://www.haskell.org/sitewiki/images/0/03/TMR-Issue7.pdf [pg. 30])

Perhaps however, I have been getting the wrong impression.  I am going to 
rework my code base using objects and see how it turns out.  On this note, 
does anyone know of a way to automatically generate the object of a module?  
Ie. I have three modules A,B and C which all implement the same module type 
X, but I really want three objects a,b and c for those modules which 
implement the same class type x, so that I can stick all objects in the same 
list and map over them etc..

I can do this by hand (not difficult, just a little tedious), but I wonder if 
there's not some camlp4 trick that can take the values in a module and just 
create a passthrough object which exposes those values.

Thanks again for all your replies.  They have helped enormously,

Peng



On Tuesday 13 November 2007 11:48:40 pm Jacques Garrigue wrote:
> From: Peng Zang <peng.zang@gmail.com>
>
> > I've come across a way to do this in haskell using what they call
> > "existential types".
> >
> >   http://www.haskell.org/haskellwiki/Existential_type
> >
> > I don't really understand existential types however and don't know if
> > OCaml has them nor how to use them.
>
> Notwithstanding your reluctance to use them, objects in ocaml are
> really what amounts to Haskell's existential types, particularly
> those for which a type class is specified. Put the other way round,
> most examples of constrained existential types (i.e. where there is a
> type class specifiying the existential) are just encodings for
> objects. The encoding of objects through existentials has been known
> for a long time. OCaml doesn't need this encoding because it has
> primitive objects.
>
> From an implementation point of view, constrained existentials need to
> be accompanied by their dictionaries, which is exactly the same thing
> as the method table in an object, so even the implementation is very
> similar.
>
> Method calls on arbitrary objects can be slow. This is because, due to
> subtyping, in some situations there is no way to know where the method
> will be in the table, and a binary search has to be done. However,
> this overhead can be avoided if all objects used in a specific method
> call have the same methods. That is, they should have the same
> interface, without using subtyping. That way, the method will be at
> the same position in all objects, and this position is cached (for
> native code).
> (Note that this also means that any benchmark on the performance of
> objects shall consider the impact of cacheing, which can be hard to
> evaluate in micro-benchmarks.)
>
> Dmitri's example had this property, so it should display good
> performance (as good as explicit existential encodings.)
>
> Jacques Garrigue


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFHOu3pfIRcEFL/JewRAnwXAKCqWM5BJ6J44jXMHzmonP5iRhqUtgCgoq6/
rg54JaQONgB/DCVf4RP4aPc=
=NP4X
-----END PGP SIGNATURE-----