Re: [Ocaml-lib-devel] Dllist

[Christophe T. <chr...@us...>]

On Sun, 29 May 2005, John Skaller <sk...@us...> wrote:
> 
> Well my view is that a *base* library provides simple efficient
> things -- it is oriented to the computer NOT the user.

In the first mail your justification calls upon "mathematics" (in a
flawed way IMHO), now you refer to the computer.  Aren't these at the
opposite ends of the spectrum?  IMO, the interface is for the user
(thus must be mathematically well defined, simple yet powerful) and
the implementation is for the computer (thus allowed to use tricks to
achieve efficiency).

> ExtLib is positioned as a replacement system library.

Precisely!  If you look at the std lib, it does not provide
e.g. balanced binary trees leaving to you the task of implementing Map
and Set.  It provides data-structure interfaces, not down to the metal
low-level libraries (use C if that's what you are after).

> The point is that you can construct a 'container' design from a
> 'nodes-only' design with a wrapper, but not the other way around,

You haven't much looked at the code, have you.  If you had, you would
have noticed that the wrapper would only use the node data-structure,
the code for all functions being different enough to mandate rewriting
them.

Also, from a point of view of efficiency, providing efficient low
level data-structures that become inefficient (compared to a direct
implementation) when wrapped to do what the user really wants is a
waste of computer and human resources.

> For example, consider two lists A and B, and you join them to create
> a list C. What happens to A and B?  With the current implementation
> as I understand it, there isn't an issue, A, B, and C are now all
> the one list.

It is quite funny to take the [splice] function as a justification for
your design when, IMO, its utility is far lower than the possibility
of having empty lists.

In fact [splice l1 l2] will leave [l1] and [l2] in invalid states when
[l1] and [l2] are lists _with_ends_.  It is not the case for
_circular_ lists -- but given the name of the module, it is my
understanding that the doubly-linked list is what is targeted.  A
circular list module [CircularList] can also be built (and different
tricks may be imagined for its implementation).

In the end, it all boils down to which ADT we want to build.  One
wants to use a library for the operations it provides (in an efficient
manner) not because it is nice to the computer.

> Also, I can't contribute any experience with the particular
> implementation in Extlib, because I don't use it.

But eventually intend to?

ChriS