Re: [Ocaml-lib-devel] Data Structures

[Nicolas C. <war...@fr...>]

> 2) Ext-Lib should include data structures which are a) non-trivial to
> implement, and b) widely (if not massively) usefull- by which I mean
> many moderately complex programs can use one or more of them profitably.
> Call this the "Java Standard Library" concept.  Note that this could
> involve more than just data structures- things like XML-Light could be
> included as well.

In the beginning of this list, I think we already talked about this point,
and concluded that ExtLib should include "modules" that are either
non-trivial to implement and widely used , or "modules" that are perhaps
very easy to implement but massively used ( the second point is important,
the goal here is to standardize a lttle more programming habits while each
user have today his own implementation )

> Personally, I'm in favor of the Java-style library, the kitchen sink
> concept.  I think that a couple of megabytes of "unnecessary" and unused
> libraries isn't that big of problem compared to the bloats and memory
> leaks of your average C++ program.

I personnally don't like the Java Stdlib : too much classes ! Too much is
becoming bad when you can't tell anymore when you need some library if it is
included in the Stdlib or not : sometimes it takes less time to write a
class from scratch than finding+learning how to use it from the Java Stdlib
:-)

> 2) It increases program efficiency by encouraging using complex data
> structure where appropriate.  Part of the reason that lists, arrays, and
> unbalanced trees are so popular is because they are trivial to
> reimplement.  Part of the reason that priority search queues are not
> popular is that they are non-trivial to implement.  This is why quicksort
> is more popular than heapsort, and bubblesort is more popular than either
> of them.

Perhaps true , but the user have to understand it ( see point 3 )

> 3) It increases awareness of the more complex data structures.  Another
> part of the reason priority search queues aren't more widely used is that
> they aren't known or understood.  Note this goes beyond just implementing
> the data structures- I have a mostly-completed "gentle introduction to
> priority search queues" kicking around at home.

I think that when you provide such a library, you have to provide a (short)
introduction for each module . Especially concerning data structures, the
user should be easily aware of what are the usage of each data structure
provided by the library. IMHO, the best would be to have a comparative list
of available data structures, with some examples of using them and
complexity notations. If that compative list cannot show the user the main
differences between 2 data structures, then one of them is useless :)

> Bit sets/arrays- although I'm begining to think this really should be an
> adjunct to arbitrary precision integers.

Perhaps two differents modules would be good, even if they share the same
internal representation , since you're not using the same way a Bitset and a
big_int. Converting from and to a Num.num should be enough. ( that reminds
me that "Big_int" and "Num" functions naming is quite "old styled" ending
all with _big_int or _num, perhaps herited from ages ago, before the module
system )

I forgot the following :
- mutable data structures:
    * Queue ( FIFO )

Nicolas Cannasse