Re: [Caml-list] adding lots of elements to a list

[Jon Harrop <jon@ffconsultancy.com>]

On Friday 02 June 2006 16:28, julien.michel@etu.univ-orleans.fr wrote:
> The number of created objects can grow very fast, and may raise an amount
> greater than 100 000 elements.

That's fine as long as you don't use the non-tail-recursive modules from the 
List module (e.g. map, fold_right).

> let count = ref 3 ;;    (* number of iteration *)
> let list = [] in
>
> while (!count > 0)  do
>   decr count;
>   let list = list@[!count] in
>   Printf.printf "The 1st element is  %i \n" (List.hd list) ;
> done;
>
> Printf.printf "list contains %i elements \n" (List.length list) ;;

To get the desired behaviour you must use a list ref and replace the list each 
iteration:

# let count = ref 3 ;;    (* number of iteration *)
  let list = ref [] in

  while (!count > 0)  do
    decr count;
    list := !list @ [!count];
    Printf.printf "The 1st element is  %i \n" (List.hd !list) ;
  done;

  Printf.printf "list contains %i elements \n" (List.length !list);;
The 1st element is  2
The 1st element is  2
The 1st element is  2
list contains 3 elements
- : unit = ()

OCaml's lists are designed to be consed and decapitated from the front, 
so "h :: t" is O(1) whereas "t @ [h]" is O(n^2). ***

Also, you might find functional style easier to use here:

# let rec make = function 0 -> [] | n -> n-1 :: make (n-1);;
val make : int -> int list = <fun>
# make 3;;
- : int list = [2; 1; 0]

That version isn't tail-recursive, so it'll raise Stack_overflow or even 
segfault if you give it a big "n":

# make 1000000;;
Stack overflow during evaluation (looping recursion?).

But you can write a tail-recursive version by accumulating the list in reverse 
order:

# let rec make a = function 0 -> List.rev a | n -> make (n-1::a) (n-1);;
val make : int list -> int -> int list = <fun>
# make [] 1000000;;
- : int list =
[999999; 999998; 999997; 999996; 999995; 999994; 999993; ...]

*** actually I think this is O(n^3) in native code.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists