Re: [Camllist] A G'Caml question" + additional info
 Krishnaswami, Neel
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20010711 (23:08) 
From:  Krishnaswami, Neel <neelk@c...> 
Subject:  Re: [Camllist] A G'Caml question" + additional info 
Brian Rogoff [mailto:bpr@best.com] wrote: > > > > For instance, I recently wrote yet another set > > implementation, because the functorial interface to the Set module > > in the standard library wouldn't let me use it in a fully polymorphic > > fashion. If the Set library had been written using OCaml's object > > system, then I would not have had to redo my own. > > That's odd. If the Set library had been implemented using the object > system, it seems that you would have less (parametric) polymorphism > since OCaml doesn't (yet?) have polymorphic methods. I don't know enough type theory to argue, except that in practice I seem to be getting more polymorphic types with objects than with functors. I guess I'll go ahead and post the example  it's possible that I just don't know enough yet! So, let's take the example of a priority queue implemented using a binary search tree. The usual functorial approach to this looks like: module type ORD = sig type t val cmp : t > t > bool end module Queue(Elt : ORD) = struct type elt = Elt.t type t = Nil  Tree of t * elt * t let empty = Nil let rec min = function  Nil > raise Not_found  Tree(Nil, x, r) > x  Tree(l, x, r) > min l let rec add x = function  Nil > Tree(Nil, x, Nil)  Tree(l, y, r) as t > if Elt.cmp x y then Tree(add x l, y, r) else if Elt.cmp y x then Tree(l, y, add x r) else Tree(l, x, r) end To specialize this a structure satisfying the ORD signature is applied to the functor. The obvious approach with classes looks very similar, except that the Elt functor argument becomes a method to be overridden: type 'a tree = Nil  Tree of 'a tree * 'a * 'a tree class virtual ['a] q = object(self) val tree = Nil method virtual cmp : 'a > 'a > bool method min = let (<) = self#cmp in let rec loop = function  Nil > raise Not_found  Tree(Nil, x, r) > x  Tree(l, x, r) > loop l in loop tree method add x = let (<) = self#cmp in let rec loop = function  Nil > Tree(Nil, x, Nil)  Tree(l, y, r) as t > if x < y then Tree(loop l, y, r) else if y < x then Tree(l, y, loop r) else Tree(l, x, r) in {< tree = loop tree >} end To specialize this we just subclass and add a cmp method. So far so good. However, suppose I have a type type 'a tag = int * 'a This is a value that has an integer priority plus some arbitrary data, and I'd like to make a priority queue that stores tagged values. Since the type 'a tag is polymorphic, AFAICT there's no way of writing a structure that satisfies the ORD signature. However, writing a class that can accept this is easy  class ['a] taggedq = object inherit ['a] q constraint 'a = 'b tag method cmp = fun a b > (fst a) < (fst b) end will Just Work(tm). This is why I called the class "more polymorphic." If my terminology is wrong, corrections will be gratefully accepted.  Neel Krishnaswami neelk@cswcasa.com  Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr