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

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

    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