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

["Krishnaswami, Neel" <neelk@cswcasa.com>]

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/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr