On Tuesday 21 September 2010 19:45:50, Daniel Seidel wrote:
Hi,
I've got the answer - its the sumLeafs function that behaves different for leftPath / rightPath. If one exchanges it in the leftPath case by
sumLeafs (Fork l r) = sumLeafs r + sumLeafs l sumLeafs (Leaf i) = i
the difference in runtime is gone.
Yes. The matter is that with the original sumLeafs (btw., that ought to be sumLeaves), the left path builds a call-tree for sumLeafs isomorphic to the tree first. Once that's complete, the evaluation proceeds from leaves to root. The right path, on the other hand, always has the call to sumLeafs for the left subtree returning without recursion, so it builds a tree of calls to (+) which is isomorphic to the original tree, 1 + (1 + (1 + (1 + ...(1 + 1)...))). Since (+) is a simpler function than sumLeafs, that call tree is apparently cheaper. For trees like these, a much better implementation of sumLeafs uses an accumulating parameter and detects leaves on the right while going down the tree: sumLeafs = smlvs 0 smlvs !acc (Leaf i) = acc+i smlvs acc (Fork l (Leaf j)) = smlvs (acc+j) l smlvs acc (Fork l r) = smlvs (smlvs acc l) r (Note there's no need to detect leaves on the left.) That sums the left and right paths in 0.02s with -O2. It'll be faster (and allocate much less) for all trees containing many very skewed subtrees (so lots of leaves with the other branch going much deeper), but for well balanced trees, it makes practically no difference.
Cheers,
Daniel.
Hey, that's *my* line!