Re: [Camllist] @, List.append, and tail recursion
 Diego Olivier Fernandez Pons
[
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:33) 
From:  Diego Olivier Fernandez Pons <DiegoOlivier.FERNANDEZPONS@c...> 
Subject:  Re: [Camllist] @, List.append, and tail recursion 
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 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