[Haskell-cafe] asymmetric runtimes for symmetric trees

[Daniel Fischer]

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!