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 <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
