Re: [Caml-list] Fwd: interval trees

[Francois Berenger <berenger@riken.jp>]

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