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 q1GAMPZN023125 for ; Thu, 16 Feb 2012 11:22:25 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Am4BAOXXPE/RVdS2imdsb2JhbABDn1WRDQgiAQEBCgkNBxIGI4FyAQEBBBICExkBGxILAQMMBgULDQ0hIgERAQUBChIGExIQh2agOQqLcYJxhHQ/gQsCBQuLRlIIAgQBBQMBCAQEGAMChB4HAg4JAwKDLgSVNo4pPYQD X-IronPort-AV: E=Sophos;i="4.73,428,1325458800"; d="scan'208";a="144529345" Received: from mail-wi0-f182.google.com ([209.85.212.182]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 16 Feb 2012 11:22:20 +0100 Received: by wibhn14 with SMTP id hn14so1922950wib.27 for ; Thu, 16 Feb 2012 02:22:20 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type:content-transfer-encoding; bh=4wXbGkiY6IQmHMCJcoOSPFOXv2wQudvg5Yv9Y5/DuQg=; b=U0EL+kNyvvYNwkjw5bDvf2kRbk5CFTsCtVUh6YHW141BQsyxQU2kok1Cp5MBHOXEnn SJHXNmWmKfAjYQV9VDrLPpyRqu8g9m4wstJgzjkMKP0EkdP3Fyu12yE0i+UQ6WsKz428 3yjrKa9BRtT2JC5Gn3BgAS24h87qPMkJCH7E8= Received: by 10.216.135.76 with SMTP id t54mr859075wei.14.1329387740212; Thu, 16 Feb 2012 02:22:20 -0800 (PST) MIME-Version: 1.0 Received: by 10.227.63.13 with HTTP; Thu, 16 Feb 2012 02:21:39 -0800 (PST) In-Reply-To: <4F3C6D08.3020706@riken.jp> 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> From: Gabriel Scherer Date: Thu, 16 Feb 2012 11:21:39 +0100 Message-ID: To: Francois Berenger Cc: caml-list@inria.fr Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id q1GAMPZN023125 Subject: Re: [Caml-list] Fwd: interval trees I can't resist giving the usual tail-recursive CPS-transformed version (untested): 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 >