Re: [Caml-list] Two types of efficiency (Was Efficiency of 'a list)

[Eray Ozkural <exa@kablonet.com.tr>]

On Monday 05 May 2003 19:38, Diego Olivier Fernandez Pons wrote:
> Keep in mind that designing a data structure library is a hard work :
> Chris Okasaki, Ralf Hinze and a lot of others have failed ; Baire has
> not even been released after 1 year of work, the geometric algorithms
> in JDSL (Java data structures library) never arrived and after 2 years
> the new version 2.1 does not provide any real improvment over 2.0.6,
> etc.
>
> The Caml standard library is in the 'not so bad' category

Structure monster will help! (^_-)

But it's almost certain that I will not write any functional structure 
library, ahem :P That's more like optimizing for an ensemble of data 
structures instead of 1 and I think it requires an expertise of its own. 
Moreover, I don't want to be labeled "failed" :) But in the imperative area, 
I will consume algorithms one by one ;)

I liked Okasaki's stuff btw, I even used those set thingies for a real quick 
hypergraph implementation (which was admittedly too slow for real life)

What I have in mind is tight imperative code like:
AVL Trees
B+ Trees
Disjoint Sets
Some dynamic hash code
PQ: Binary Heaps, etc. (I already did binary heap)
k-d trees (I'm not sure if I wanna go into comp. geometry though ;) )

So my clients will be speed demons who are not concerned with functional 
beauty of their basic data expressions. OTOH, I will demonstrate that 
imperative code can be elegant!!!

I don't know, what else is left in the world? It's so easy to program in ocaml 
that I think I will do all of these and more this summer. (Complete with 
those pretty running time bounds)

Assume I'm writing something like that, people don't want it to be functors 
but simply polymorphic types, is that so? While coding I had the impression 
that most of the data structures would fit into a functor-ful style. (same 
goes for haskell classes)

Is these concerns because people are tired of the rather redundant means with 
which one is obliged to instantiate a data structure using functors?

For instance if you're doing a priority queue, you want to know at least three 
things:
1) What is the type of key?
2) What is the type of record?
3) How do I compare them?

Not too different from what Set module wants.

I even had the wild idea of higher and higher level of abstractions but I 
don't know where those abstractions would start to bog down the code yet. As 
I said defining Set like the exactly mathematical way, and then defining 
implementation classes of sets, and then implementations will be the 
beginning that path of "i want more" kind of abstractions ;)

And a good, in fact, very good thing about abstractions is that I can make a 
framework that can incorporate other people's code so that I won't have to 
write the whole world from scratch! I think that's a very nice idea since 
even I have a finite appetite for coding! I'm also right now developing a bad 
feeling that the "framework" design might be harder than it sounds...

Cheers,

-- 
Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara  KDE Project: http://www.kde.org
www: http://www.cs.bilkent.edu.tr/~erayo  Malfunction: http://mp3.com/ariza
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners