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 SAA29696; Fri, 31 Jan 2003 18:33:52 +0100 (MET) 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 SAA29615 for ; Fri, 31 Jan 2003 18:33:51 +0100 (MET) 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 h0VHXoP25017 for ; Fri, 31 Jan 2003 18:33:50 +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 h0VHXoYY006405 for ; Fri, 31 Jan 2003 18:33:50 +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 SAA06884 for ; Fri, 31 Jan 2003 18:32:42 +0100 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id SAA4612164 for ; Fri, 31 Jan 2003 18:32:41 +0100 Date: Fri, 31 Jan 2003 18:32:41 +0100 (NFT) From: Diego Olivier Fernandez Pons To: caml-list@inria.fr Subject: Re: [Caml-list] @, List.append, and tail recursion 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, Brian Hurt wrote : > Here's an example I have run across. I'm working with sparse vectors, and > basically storing them as (int * float) lists. Now, let's write the > vector add function. The naive implementation would be: let rec add_rec result = fun a b -> match (a, b) with | ([], _) -> a @ result | (_, []) -> b @ result | ((n, x) :: a_tail, (m, y) :: b_tail) -> match compare m n with | k when k < 0 -> add_rec ((n, x) :: result) a_tail b | k when k > 0 -> add_rec ((m, y) :: result) a b_tail | _ -> add_rec ((n, x +. y) :: result) a_tail b_tail This is a tail recursive version of your function. The main problem is that it reverses the list every time it is called. Your first idea is to define let add = fun a b -> List.rev (add_rec a b) and you are right when you say that you are allocating a lot of memory. But you can do much better : add_rec only needs the two lists to be sorted, not to be increasing. Why don't you try type vector = | Increasing of (int * float) list | Decreasing of (int * float) list then you just have to write the 4 corresponding add functions Here is a second idea : is there a way to implement add in such a way that it does not need the two arguments to be sorted ? If you were working with arrays this would not be difficult. Then, just try functional random acces lists. They give you a O(1) access to the head element (in case both list are sorted in the same way) or O(log n) acces to any element. 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