From mboxrd@z Thu Jan 1 00:00:00 1970 X-Sympa-To: caml-list@inria.fr Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id q1H8DQp4032384 for ; Fri, 17 Feb 2012 09:13:26 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ApcCAPMKPk/BMH5JmWdsb2JhbABEgw6taiIBAQEBAQgLCwcUJ4FyAQEEASc+ExELIRYPCQMCAQIBRRMIAod7A7kwi2sKFQcBEAICBQMCAwcEBAICAwQQCYM/Ji6DHQSbFI0M X-IronPort-AV: E=Sophos;i="4.73,434,1325458800"; d="scan'208";a="144707312" Received: from dsi-mta-out.univ-savoie.fr ([193.48.126.73]) by mail1-smtp-roc.national.inria.fr with ESMTP; 17 Feb 2012 09:13:22 +0100 Received: from localhost (localhost [127.0.0.1]) by dsi-mta-out.univ-savoie.fr (Postfix) with ESMTP id A2593300B7 for ; Fri, 17 Feb 2012 09:13:21 +0100 (CET) X-Virus-Scanned: Debian amavisd-new at dsi-a177.univ-savoie.fr Received: from dsi-mta-out.univ-savoie.fr ([127.0.0.1]) by localhost (dsi-mta-out.univ-savoie.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id eWy7fbBUAUVv for ; Fri, 17 Feb 2012 09:13:21 +0100 (CET) Received: from dsi-mail-msa1.univ-savoie.fr (dsi-mail-msa1.univ-savoie.fr [193.48.126.83]) by dsi-mta-out.univ-savoie.fr (Postfix) with ESMTP id 8FA8930065 for ; Fri, 17 Feb 2012 09:13:21 +0100 (CET) Received: from localhost (localhost [127.0.0.1]) by dsi-mail-msa1.univ-savoie.fr (Postfix) with ESMTP id 8BF6D1C087 for ; Fri, 17 Feb 2012 09:13:21 +0100 (CET) X-Virus-Scanned: Debian amavisd-new at dsi-mail-msa1 Received: from dsi-mail-msa1.univ-savoie.fr ([127.0.0.1]) by localhost (dsi-mail-msa1.univ-savoie.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id UDCKoJQW5ctN for ; Fri, 17 Feb 2012 09:13:21 +0100 (CET) Received: from [192.168.144.6] (bin73-1-78-240-16-62.fbx.proxad.net [78.240.16.62]) by dsi-mail-msa1.univ-savoie.fr (Postfix) with ESMTPSA id 52F801C086 for ; Fri, 17 Feb 2012 09:13:21 +0100 (CET) Message-ID: <4F3E0BC4.7030702@univ-savoie.fr> Date: Fri, 17 Feb 2012 09:11:48 +0100 From: Christophe Raffalli User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.24) Gecko/20111114 Iceowl/1.0b2 Icedove/3.1.16 MIME-Version: 1.0 To: caml-list@inria.fr References: <4F346DB9.2070303@riken.jp> <20120210182914.GA17498@annexia.org> <87wr7tb77z.fsf@frosties.localnet> <4F36AA45.1070502@colba.net> <4F38D455.1040204@irisa.fr> <4F3B0A46.3070105@riken.jp> <87mx8kruk1.fsf@frosties.localnet> <4F3C6AB4.6090100@riken.jp> <4F3C6D08.3020706@riken.jp> <4F3DA68F.1030402@riken.jp> In-Reply-To: <4F3DA68F.1030402@riken.jp> X-Enigmail-Version: 1.1.2 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Validation-by: christophe.raffalli@univ-savoie.fr Subject: Re: [Caml-list] Fwd: interval trees -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hello, > > Thanks! That's the technique I was looking for > (Continuation Passing Style), as I may have to use > this on some other algorithms in the future. > >> let interval_tree intervals = >> let rec interval_tree intervals k = >> match intervals with >> | [] -> k Empty >> | _ -> >> let x_mid = median intervals in >> let left, mid, right = partition intervals x_mid in >> let left_list = L.sort leftmost_bound_first mid in >> let right_list = L.sort rightmost_bound_first mid in >> interval_tree left (fun left_tree -> >> interval_tree right (fun right_tree -> >> k (Node(x_mid, left_list, right_list, left_tree, >> right_tree)))) >> in interval_tree intervals (fun t -> t) There is still one non tail-rec call, and this will basically rebuild the stack in the heap, with more GC work. So unless you know your trees are non balanced and left branch are deeper, this code is probably worst. In the old days (I think now OCaml is clever), It could save some stack space (and this could retain some pointer), to do the last call by another function : let rec interval_tree intervals = match intervals with [] -> Empty | _ -> let x_mid = median intervals in let left, mid, right = partition intervals x_mid in let left_list = L.sort leftmost_bound_first mid in let right_list = L.sort rightmost_bound_first mid in last_call x_mid left_list right_list left right and last_call x_mid left_list right_list left right = Node (x_mid, left_list, right_list, interval_tree left, interval_tree right) Here it makes sure mid and intervals are not stored in the stack frame ... But it may be done anyway now, I am not sure. Someone knowns the current rules to know what's retain on the stack in today OCaml ? Cheers, Christophe -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAk8+C8MACgkQi9jr/RgYAS4nHwCfYX9mY8nHAkz65QQXDerPwfHd tvgAoIjvVxlDONYRjwpSZS0/5LhhCo44 =OnkD -----END PGP SIGNATURE-----