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 q1G8xgr2019611 for ; Thu, 16 Feb 2012 09:59:42 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ah8DAOPEPE/ZSMDdjmdsb2JhbABDsGoiAQEBAQkLCQkSBSSBcgEBBAEnEz8FCwshJQ8BBCghE4d/A7VfjB4LCQUBAgkICwoDAQICg20CBUEMgzAEmwCNHw X-IronPort-AV: E=Sophos;i="4.73,428,1325458800"; d="scan'208";a="131595482" Received: from fmmailgate01.web.de ([217.72.192.221]) by mail4-smtp-sop.national.inria.fr with ESMTP; 16 Feb 2012 09:59:37 +0100 Received: from moweb001.kundenserver.de (moweb001.kundenserver.de [172.19.20.114]) by fmmailgate01.web.de (Postfix) with ESMTP id 2ED991AAE32BC for ; Thu, 16 Feb 2012 09:58:00 +0100 (CET) Received: from frosties.localnet ([95.208.118.96]) by smtp.web.de (mrweb002) with ESMTPA (Nemesis) id 0ML8F7-1RyE902Uu9-000Z1C; Thu, 16 Feb 2012 09:57:59 +0100 Received: from mrvn by frosties.localnet with local (Exim 4.77) (envelope-from ) id 1RxwnA-0007jK-8e; Thu, 16 Feb 2012 09:34:16 +0100 From: Goswin von Brederlow To: Francois Berenger Cc: 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> Date: Thu, 16 Feb 2012 09:34:16 +0100 In-Reply-To: <4F3C6D08.3020706@riken.jp> (Francois Berenger's message of "Thu, 16 Feb 2012 11:42:16 +0900") Message-ID: <87y5s3mb1z.fsf@frosties.localnet> User-Agent: Gnus/5.110009 (No Gnus v0.9) XEmacs/21.4.22 (linux, no MULE) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Provags-ID: V02:K0:N5Ay2oqTTiwY00/xBaRThylxk6DMH/+HI9X61zHLugg +VPCKMxlyvH8+FPJPiTGuYx0rQThYISvAwSdyN2K7bo1akigZ4 xOrlJrSo8Q+xT7tjWLfiOz9nfKZ0g8nrcE0+8yuoxahHTG6qbu SrC5NGj65oV/URzOmMy5VjdzW6jmo2iIXbfaw5EDUCzXRBUJ4+ 2qYT7F75lx6rfPOvaP4xQ== Subject: Re: [Caml-list] Fwd: interval trees Francois Berenger writes: > 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. Each recursion halves the lists, right? That means you need a very very very long list to exceed the recursion depth. MfG Goswin