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