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

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

Markus Mottl [mailto:markus@mail4.ai.univie.ac.at] wrote:
> 
> 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.

He has some timing data comparing splay trees, balanced binary 
trees, Patricia tries, and red-black trees in his paper "Fast 
Mergeable Integer Maps." To summarize, red-black trees were the 
fastest on lookup, and second-fastest on insertion. But they don't
perform very well on the merge operation. (These are all fairly
tuned implementations, though.)

I've been curious about implementing randomized treaps and seeing
how well they do, since they seem simpler than any other balanced 
binary tree implementation.

> > > 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.

Applying a functor doesn't bother me. What I find annoying is the
need to functorize my own code if I want to write functions that 
work independently of the element type. It doesn't take very many
of these before my source contains more functor declarations than
actual code. 

A sufficiently powerful include facility for G'Caml can make this
problem go away, since you could define a generic and have each 
functor instantiation add its specialized methods automatically
to the generic. 

> > 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.

Oh, I see what you mean. That's true but since I'd only implement the
Set once I don't much care. I tend to worry more about cruft associated
with code that uses the library.

--
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