[Camllist] @, List.append, and tail recursion
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20030131 (17:06) 
From:  Diego Olivier Fernandez Pons <DiegoOlivier.FERNANDEZPONS@c...> 
Subject:  Re: [Camllist] @, List.append, and tail recursion 
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 : joinlists, catenable lists, doublelinked 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 website (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 = <fun> > I agree that this is recurring problem, I myself often get bit by > List.map > > It makes it very easy to make nonscalable 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 bytecode 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 camllistrequest@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners