From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id q1G2gPM6001082
	for <caml-list@sympa-roc.inria.fr>; Thu, 16 Feb 2012 03:42:25 +0100
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AqsDAJ1rPE+GoCGhnGdsb2JhbABDgw6tfQEBAQEBCAsJCRQngXMBBScRQBELIRYPCQMCAQIBRRMIAQHBQIwCFwECBwgCBAEFAwEIBAcPAwMBAgKDbQdggx0EiEuMa4VdjRo
X-IronPort-AV: E=Sophos;i="4.73,426,1325458800"; 
   d="scan'208";a="131544515"
Received: from postman1.riken.jp (HELO postman.riken.jp) ([134.160.33.161])
  by mail4-smtp-sop.national.inria.fr with ESMTP; 16 Feb 2012 03:42:19 +0100
Received: from postman.riken.jp (postman1.riken.jp [127.0.0.1])
	by postman.riken.jp (Postfix) with SMTP id C32892588001
	for <caml-list@inria.fr>; Thu, 16 Feb 2012 11:42:16 +0900 (JST)
Received: from [172.27.98.103] (rikad98.riken.jp [134.160.214.98])
	by postman.riken.jp (Postfix) with ESMTPA id 5CA8D32A008B
	for <caml-list@inria.fr>; Thu, 16 Feb 2012 11:42:16 +0900 (JST)
Message-ID: <4F3C6D08.3020706@riken.jp>
Date: Thu, 16 Feb 2012 11:42:16 +0900
From: Francois Berenger <berenger@riken.jp>
User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.26) Gecko/20120131 Thunderbird/3.1.18
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>
In-Reply-To: <4F3C6AB4.6090100@riken.jp>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-PMX-Version: 5.6.0.2009776, Antispam-Engine: 2.7.2.376379, Antispam-Data: 2012.2.15.183615
Subject: Re: [Caml-list] Fwd: interval trees

Hello,

Anyone can translate this into being tail recursive
if it's possible:

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
         Node (x_mid,
               left_list, right_list,
               interval_tree left, interval_tree right)

I'm afraid my program could crash on a very long list of intervals.

Thanks a lot,
F.