Re: [Caml-list] Set/Map with intervals and/or order-related operations

[Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@etu.upmc.fr>]

    Bonjour,

> Structure monster just got out of a computational geometry project
> disaster so he can't really help in a substantial way (^_^)

Sometime ago I answered to a comment of Oleg Trott in private, since I
felt it wasn't really interesting for the other users of the caml-list
but if this experience can help...

Oleg Trott wrote :

>> Baire has not even been released after 1 year of work,
>
> I understand that you are not designing new algorithms, but coding
> up ones that are well-known. If so, what is the limiting factor in
> your work : trying to anticipate what features users might and might
> not need ?

The first point is not absolutely true : Baire contains a useless
generalization of balancing schemes, a few operations on zippers,
graph data structure based on ternary balanced trees (both inspired by
Gerard Huet's Zen library), lexical maps, there were dynamic optimal
trees (see the art of computer programming for the statical version)
based on Cartesian trees... But this is not the problem.

The main problems are :
- lack of knowledge
- lack of time
- lack of organization

And the worse is the last one.

I wanted to write a library of NP-hard approximation algorithms over
Baire's graph data structures. I soon understood I would need a
LP-solver and an efficient branch-and-bound scheme.

I then experimented on branch-and-bound (huge trees) with two
techniques : continuations (simulated by exceptions) and zippers.
Wrote some code. I also experimented a few LP algorithms mostly on
Bender's decomposition to obtain a quasi-recursive scheme and to be
able to use a persistent data structure (sparse arrays). Wrote
some code.

The LP-algorithms had numerical unstability problems. I investigated
how to face this kind of problem (interval arithmetic, stochastic
arithmetic, regressive analysis). Chose CESTAC (stochastic arithmetic)
and wrote some code.

I also investigated a few tree traversal algorithms (classical
depth-first and best-first but also limited discrepancy search,
bounded-depth discrepancy seach, interleaved-discrepancy search, ...)

Tired of being rewriting trivial data structure (trees, heaps) because
I needed an immediate acces to X where X could be { the size, the
depth on the tree, the number of left segment in the path, ... } I
said to myself "wrong way...  automatic code generation is the only
truth".

Worked on automata (pda, lpda), attribute grammars and code
generation/specialisation. Wrote some code.

Result :
- a lot of pieces of unrelated code
- no library, not even a single line of code directly related to the
initial goal
- Baire hasn't been maintained and developed as it should have

This is the classical scheme of the 'library project disaster'.


        Diego Olivier

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