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<beren...@riken.jp> 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
-- 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
