Re: [Caml-list] @, List.append, and tail recursion

[Diego Olivier Fernandez Pons <Diego-Olivier.FERNANDEZ-PONS@cicrp.jussieu.fr>]

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

> 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