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 SAA28441; Fri, 31 Jan 2003 18:06:41 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA29130 for ; Fri, 31 Jan 2003 18:06:40 +0100 (MET) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h0VH6df07541 for ; Fri, 31 Jan 2003 18:06:39 +0100 (MET) Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.5/jtpda-5.4) with ESMTP id h0VH6dYY085307 for ; Fri, 31 Jan 2003 18:06:39 +0100 (CET) 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 SAA06674 for ; Fri, 31 Jan 2003 18:05:30 +0100 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id SAA4210892 for ; Fri, 31 Jan 2003 18:05:30 +0100 Date: Fri, 31 Jan 2003 18:05:30 +0100 (NFT) From: Diego Olivier Fernandez Pons To: caml-list@inria.fr Subject: Re: [Caml-list] @, List.append, and tail recursion In-Reply-To: <11707E79-34C2-11D7-9ECD-000393BA7EBA@wetware.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Antivirus: scanned by sophie at shiva.jussieu.fr Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Bonjour, Some comments on various contributions to this thread Brian Hurt wrote : > I'm basically doing sparse vector/matrix stuff, handling > (effectively) (colno * value) list for vectors, and (rowno * vector) > list for matrix. And I may be hitting lists long enough to trip the > problem. If you are doing sparse matrix operations and you still hit lists long enough to cause a stack overflow, then your matrix must be really huge. If the ordrer of the terms does not matter (or if you can manage with the position information you keep in your sparse matrix) then you just need to write tail recursive functions, not taking care of the list being reversed let rec rev_map f result = function | [] -> result | head :: tail -> rev_map (f head) tail An other solution is to use a suitable data structure for your application : join-lists, catenable lists, double-linked lists ... There are not many applications in which you just can't work around in a simple way... In fact, the only one I know is Grobner bases computation, because : - the ordering on monomials really matters - you have to handle a huge amount of information, even for small systems In this case, the only solution is to write you program in C/assembler, with your own memory manager Here is a extract of FGb web-site (http://calfor.lip6.fr/~jcf/Software/index.html) Limitations * The size of the matrix in the F4 are limited to 50 000 x 50 000. * The size of the biggest coefficient in the result is limited to 9000 digits. * All the input polynomials must be expanded Most of reasonable computations (even in computer algebra) can be made in a functional language. Many computer algebra systems are written in Lisp, and FOC (Formal + OCaml + Coq) should be soon avaible (spring 2003) That is why I suspect you may not be using the best data structures and algorithms avaiable. Could you explain what you are working on ? Christophe Raffalli wrote : > May be rev_append could be added to the list module (despite the > fact it is trivial to write it yoursleft) ? ??? Objective Caml version 3.06 # List.rev_append;; - : 'a list -> 'a list -> 'a list = > I agree that this is recurring problem, I myself often get bit by > List.map > > It makes it very easy to make non-scalable program, works for input > less that 1000 elements, and the when applied to a large problem it > fails without a trace. It is very difficult to find the location of > the problem if you use the native compiler, and most of these > programs doesn't even work using the byte-code compiler. > > So one of my coding guidelines is: > - do not use List.map > > I would like a prefer other solutions If your program does not work for input less than 1000, this probably means a poor design. You may be using lists where other data structure should be used. Could you give me code examples ? I could then add an adequate data structure to Baire. James woodyatt wrote : > For grins, I wrote an equivalent test program. It uses a functional > deque instead of a list. (I have written one. It's a component of my > Cf library, which remains unreleased at the moment. Markus Mottl has > translated several of Chris Okasaki's functional queue > implementations into Ocaml, and you can find them on the Hump.) You will find in Chris Okasaki's thesis/book several implementations of catenable lists and many references. One of them embedds a queue in a tree which seems to be what you are looking for (head in O(1), append in O(1)) I wrote a linearisation of Okasaki's data structure. It has not been revised yet then there could be some bugs. 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