[Camllist] My function is too eager
 Diego Olivier Fernandez Pons
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20040413 (10:42) 
From:  Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@e...> 
Subject:  [Camllist] My function is too eager 
Bonjour, I have to compute statistics over all the subtrees of a tree keeping generality and efficiency. The function I have written is clearly too eager but I haven't been able to rewritte it in a proper lazy way because the lazyness I need seems to be "transversal". The problem is to count all subtrees having a property (P) which is checked via a boolean function f : int > int > int > int > bool where the first four parameters are the  shortest path of the tree  longest path of the tree  size of the tree  total path lengt of the tree all computed incrementally in a bottomup manner. Then, they have to be sorted according to a parameter among these. example : avl_subtrees Shortest x;;  : (int * int * int) list = [(1, 50, 501); (2, 21, 251); (4, 13, 63); (5, 3, 31); (6, 1, 16); (7, 0, 8); (8, 0, 4); (9, 1, 2)] means that in the tree x there are 501 subtrees of shortest path equal to 1 and 50 of them are avl trees, etc. I wrote the following code. It just computes the data incrementally, checks the boolean function and updates the counters (a bag  insertion increments the counter if the element is already there). type evaluation = Shortest  Longest  Size  Average let extract_statistics = function stats > DoubleBag.fold_right (fun k v v' l > (k, v, v') :: l) stats [] (* Core function strict version *) let make_distribution_function = fun f statistic_mode > let rec subtree bag = function  E > (0, 0, 0, 0, bag)  N (l, v, r, _) > let (l_shortest, l_longest, l_size, l_total, bag') = subtree bag l in let (r_shortest, r_longest, r_size, r_total, bag'') = subtree bag' r in let shortest = 1 + min l_shortest r_shortest and longest = 1 + max l_longest r_longest and size = 1 + l_size + r_size and total = 1 + l_size + r_size + l_total + r_total in let parameter = match statistic_mode with  Shortest > shortest  Longest > longest  Size > size  Average > total / (size + 1) in (shortest, longest, size, total, if f l_shortest r_shortest l_longest r_longest l_size r_size then DoubleBag.insert_both parameter bag'' else DoubleBag.insert_two parameter bag'') in subtree let make_subtrees = fun f mode tree > let (_, _, _, _, stats) = (make_distribution_function f mode) DoubleBag.empty tree in extract_statistics stats (* boolean function examples *) let avl_subtrees = fun mode tree > make_subtrees (fun _ _ ll lr _ _ > abs (ll  lr) <= 1) mode tree let red_black_subtrees = fun mode tree > make_subtrees (ls rs ll rl _ _ > ls <= 2 * ll && rs <= 2 * rl) mode tree etc. One can see that only part of the data will be really used fun _ _ ll lr _ _ > abs (ll  lr) <= 1 therefor I made my function lazy applying a classical transformation let shortest = lazy (1 + min (force l_shortest) (force r_shortest)) longest = lazy (1 + max (force l_longest) (force l_longest)) ... in but computing these lazily is not faster than their strict counterpart. What I would need is to make lazy the complete incremental computation "data by data" and not "level by level". Does anyone have an idea of how I could achieve this ? Cordialement, Diego Olivier  To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners