This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Re: [Caml-list] A G'Caml question" + additional info
• Krishnaswami, Neel
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2001-07-11 (23:08) From: Krishnaswami, Neel Subject: Re: [Caml-list] 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
else if Elt.cmp y x then
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

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

```