This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Re: [Caml-list] @, List.append, and tail recursion
• Diego Olivier Fernandez Pons
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2003-01-31 (17:33) From: Diego Olivier Fernandez Pons Subject: Re: [Caml-list] @, 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

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)