From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <jon@ffconsultancy.com>
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39])
	by yquem.inria.fr (Postfix) with ESMTP id 3E443BB84
	for <caml-list@yquem.inria.fr>; Sat,  3 Jun 2006 00:06:35 +0200 (CEST)
Received: from pih-relay04.plus.net (pih-relay04.plus.net [212.159.14.131])
	by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id k52M6XGB012850
	(version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NO)
	for <caml-list@yquem.inria.fr>; Sat, 3 Jun 2006 00:06:35 +0200
Received: from [80.229.56.224] (helo=chetara)
	 by pih-relay04.plus.net with esmtp (Exim) id 1FmHmg-0004Yl-Bw
	for caml-list@yquem.inria.fr; Fri, 02 Jun 2006 23:06:22 +0100
From: Jon Harrop <jon@ffconsultancy.com>
Organization: Flying Frog Consultancy Ltd.
To: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] adding lots of elements to a list
Date: Fri, 2 Jun 2006 23:06:09 +0100
User-Agent: KMail/1.9.1
References: <1149262126.4480592e24237@webmailetu.univ-orleans.fr>
In-Reply-To: <1149262126.4480592e24237@webmailetu.univ-orleans.fr>
MIME-Version: 1.0
Content-Type: text/plain;
  charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Message-Id: <200606022306.10022.jon@ffconsultancy.com>
X-Miltered: at concorde with ID 4480B669.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Spam: no; 0.00; univ-orleans:01 iteration:01 decr:01 printf:01 printf:01 iteration:01 decr:01 ocaml's:01 rec:01 val:01 stack:01 segfault:01 stack:01 recursion:01 rec:01 
X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled 
	version=3.0.3

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