factorizing a tree

[Jan Skibinski]

I need some help with some optimization of certain trees:

data Tree
    = Leaf Item 
    | Product Tree Tree 
    | Sum (Double, Tree) (Double, Tree)
 
with this additional "collating" property:
	
Sum (Double, Leaf Item) (Double, Leaf Item) ==> Leaf Item

I have certain control over the shape of such trees.
I love products, but sums are expensive and hence my goal is
to avoid them at all cost. If this is unavoidable then I try
to push the sums down the tree as deeply as possible. By
doing that I am sometimes able to collate a sum of two leafs
into one leaf, and that's great. But even without the collation
effect a deeply set sum is still better than the top sum.

One of the functions, f say, is given two indices i, j
from the range (1, depth of the tree). It should modify
the layer "j" based on the information contained in the layer "i"
- producing new tree of the same depth. A naive solution
looks like this: 

f :: Int -> Int -> Tree -> Tree
f i j tree = Sum (1, g i j tree) (1, h i j tree)
where
    g = ...
    h = ...	
	
but this is the most costly solution.

One way of pushing the sums down the tree is to do something
of this sort:

f i j (Product t1 t2)
    | (i <= d) && (j <= d) = Product (f i j t1) t2
    | (i > d) && (j > d)   = Product t1 (f (i-d) (j-d) t2)
    | ....
    where
	d = depth t1
	depth t = ...	

I wonder if there are some known practises for handling such
problems. Or am I overlooking some very simple solution?
If I did not clearly specify the problem it is probably because
I did not want to post here too much of irrelevant information.
I can clarify it if required. 

Jan