From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id KAA28690; Mon, 26 May 2003 10:00:36 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id KAA28555 for ; Mon, 26 May 2003 10:00:35 +0200 (MET DST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h4Q80ZT22360 for ; Mon, 26 May 2003 10:00:35 +0200 (MET DST) Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.9/jtpda-5.4) with ESMTP id h4Q80Rru099706 ; Mon, 26 May 2003 10:00:28 +0200 (CEST) Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id JAA17938 ; Mon, 26 May 2003 09:59:36 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id JAA2252926 ; Mon, 26 May 2003 09:59:35 +0200 Date: Mon, 26 May 2003 09:59:35 +0200 (DST) From: Diego Olivier Fernandez Pons To: erayo@cs.bilkent.edu.tr cc: caml-list@inria.fr Subject: Re: [Caml-list] Set/Map with intervals and/or order-related operations In-Reply-To: <200305251348.20949.exa@kablonet.com.tr> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Spam: no; 0.00; pons:01 etu:99 caml-list:01 oleg:01 baire:01 experimented:01 sparse:01 arrays:01 fernandez:01 arithmetic:01 face:98 trivial:01 olivier:02 rewriting:02 tree:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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