From mboxrd@z Thu Jan 1 00:00:00 1970 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 q1H109kp013388 for ; Fri, 17 Feb 2012 02:00:09 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AmgCAPSlPU+GoCGhhWdsb2JhbABEgw6cSpE1AQEBCgsLBRYngXIBAQQBJxE2CgYLCxgJBBIPCQMCAQIBMxITBgIBAQ6HbQm5JYttCA0SDgEBBgYCCAIGBAICBw0BBgMCg2EBMQYEEQ6DHQSITIxrhV2NGg X-IronPort-AV: E=Sophos;i="4.73,433,1325458800"; d="scan'208";a="144667679" Received: from postman1.riken.jp (HELO postman.riken.jp) ([134.160.33.161]) by mail1-smtp-roc.national.inria.fr with ESMTP; 17 Feb 2012 02:00:02 +0100 Received: from postman.riken.jp (postman1.riken.jp [127.0.0.1]) by postman.riken.jp (Postfix) with SMTP id 6CE9832C01F0 for ; Fri, 17 Feb 2012 09:59:59 +0900 (JST) Received: from [172.27.98.103] (rikad98.riken.jp [134.160.214.98]) by postman.riken.jp (Postfix) with ESMTPA id 5998E32A008B for ; Fri, 17 Feb 2012 09:59:59 +0900 (JST) Message-ID: <4F3DA68F.1030402@riken.jp> Date: Fri, 17 Feb 2012 09:59:59 +0900 From: Francois Berenger 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> <4F3C6D08.3020706@riken.jp> In-Reply-To: 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.17.2117 Subject: Re: [Caml-list] Fwd: interval trees On 02/16/2012 07:21 PM, Gabriel Scherer wrote: > I can't resist giving the usual tail-recursive CPS-transformed version > (untested): 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) > > But see Goswin's remark: if non-tailrec makes your stack grow in > log(n) only, there is no point in jumping through hoops to get a > tail-recursive version. > > On Thu, Feb 16, 2012 at 3:42 AM, Francois Berenger wrote: >> 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. >> >> -- >> Caml-list mailing list. Subscription management and archives: >> https://sympa-roc.inria.fr/wws/info/caml-list >> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners >> Bug reports: http://caml.inria.fr/bin/caml-bugs >>