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

[Markus Mottl <markus@mail4.ai.univie.ac.at>]

On Thu, 12 Jul 2001, Krishnaswami, Neel wrote:
> If desired, I can offer a red-black tree implementation that implements
> the whole Map and Set interfaces. (I wonder how many other people have
> been inspired by that Okasaki paper?)

Having tried RedBlackSet as presented in Okasaki's book a while ago,
I was rather disappointed. It didn't perform faster (rather slower)
than the Set-module (balanced binary trees) on some quick examples that
I had tried. But maybe my simple tests were not representative.

> > Note that the non-polymorphic version also has advantages for 
> > users: e.g. they don't have to pass around comparison functions 
> > all the time.
> 
> ??? I don't understand this. In both the object version I posted 
> and the functorial version that Brian Rogoff posted, a hacker
> only needs to mention the comparison function when creating the
> type, and then never again when making or using trees.

In the functorial version you naturally have to use a functor application.
I meant a polymorphic implementation without functors, since I think
you had complained somewhere about having to apply functors. This was
probably not obvious from my text.

> In fact, my first experiment along these lines was to use a record
> with a tree and a comparison function in it. But even there, one
> could use currying to mention the function comparison only once.
> (I rejected it because it permitted trees with different but type-
> compatible comparison functions to intermix.)

But you have to manually curry every Set-function you want to use at
least once. The functor application creates the closures for the whole
Set-module at once.

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
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