Re: [Caml-list] A G'Caml question" + additional info

[Brian Rogoff <bpr@best.com>]

On Wed, 11 Jul 2001, Krishnaswami, Neel wrote:
> 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! 

In the example you post you write the classes polymorphically yet you 
write the module definition monomorphically, so of course the class will 
be more polymorphic. What you want is a polymorphic set (which you can
hack from the source to the library) to be part of the library. 

> 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

try 

module type PolyOrdSig = sig 
  type 'a t val 
  cmp : 'a t -> 'a -> bool 
end

and modify Queue in a similar fashion. 

This 

> module Queue(Elt : ORD) =
>   struct
>     type elt = Elt.t
>     type t = Nil | Tree of t * elt * t

etc. 

is something you have to explicitly instantiate. It's like an Ada generic  
or C++ class template but it isn't polymorphic. This is 

> module Queue(Elt : ORD) =
>   struct
>     type 'a elt = 'a Elt.t
>     type 'a t = Nil | Tree of 'a t * 'a elt * 'a t

what the top of your polymorphic queue module will look like. 

> 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

The analogous design would use a concrete type, and maybe be wrapped in a
functor if you wanted to generalize the element type without making it
polymorphic :-).

[...snip..]
> However, suppose I have a type 
> 
> type 'a tag = int * 'a

If you hadn't declared your class with a 'a but had used some concrete
type instead you'd be stuck in the class case too. 

> will Just Work(tm). This is why I called the class "more polymorphic."
> If my terminology is wrong, corrections will be gratefully accepted. 

Your terminology is fine, but I think if you create polymorphic modules 
you'll find that there is more parametric polymorphism available there.
If you have a sequential collection class parameterized by the element
type how would you write a fold method? 

That's not to say that objects don't have other compensating features...

-- Brian


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr