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