Re: [Caml-list] Fwd: interval trees

[Christophe Raffalli <christophe.raffalli@univ-savoie.fr>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


Hello,

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

There is still one non tail-rec call, and this will basically rebuild
the stack in the heap, with more GC work. So unless you know your trees
are non balanced and left branch are deeper, this code is probably worst.

In the old days (I think now OCaml is clever), It could save some stack
space (and this could retain some pointer), to do the last call by
another function :

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
         last_call x_mid  left_list right_list left right

and last_call x_mid  left_list right_list left right =
         Node (x_mid,
               left_list, right_list,
               interval_tree left, interval_tree right)

Here it makes sure mid and intervals are not stored in the stack frame
... But it may be done anyway now, I am not sure.

Someone knowns the current rules to know what's retain on the stack in
today OCaml ?

Cheers,
Christophe

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk8+C8MACgkQi9jr/RgYAS4nHwCfYX9mY8nHAkz65QQXDerPwfHd
tvgAoIjvVxlDONYRjwpSZS0/5LhhCo44
=OnkD
-----END PGP SIGNATURE-----