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