[Haskell-cafe] asymmetric runtimes for symmetric trees
daniel.is.fischer at web.de
Tue Sep 21 15:56:03 EDT 2010
On Tuesday 21 September 2010 19:45:50, Daniel Seidel wrote:
> 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
For trees like these, a much better implementation of sumLeafs uses an
accumulating parameter and detects leaves on the right while going down the
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.
Hey, that's *my* line!
More information about the Haskell-Cafe