Andrew Coppin wrote:
The size of the deepest possible *balanced* tree with N leaves is log2 N. The deepest possible *unbalanced* tree has N nodes!
My God... even when I correct myself I make mistakes! >_< Anyway, I eventually got my program to work. But it's absurdly slow. So I'm looking at ways to make it faster. You'll recall I wanted to construct all possible expressions from a set of numbers. The trouble is, the set of ALL possible expressions turns out to be vast - 33.6 million, roughly. It takes forever to check them all. Part of the problem is that the computer considers x + y and y + x to be two seperate expressions, when in fact they are completely equivilent. On the other hand, x - y and y - x are most certainly NOT equivilent. I am currently sitting down and trying to write some code that does the construction correctly, based on some basic algebraic properties of the four functions of arithmetic. I'm hoping that if I can get it so that fewer expressions are generated, I will have a smaller search space to test. (Of course, one way would be to generate all possible trees and then throw away "equivilent" ones - but that would be orders of magnitude slower still!) In the code I'm currently working on, I've come up with this: type Pick x = (x,[x]) type Picks x = ([x],[x]) pick :: [x] -> [Pick x] pick = pick_from [] pick_from :: [x] -> [x] -> [Pick x] pick_from ks [] = [] pick_from ks (x:xs) = (x, ks ++ xs) : pick_from (ks ++ [x]) xs picks :: [x] -> [Picks x] picks [] = [] picks [x] = [([],[x]), ([x],[])] picks (x:xs) = do (as,bs) <- picks xs [(as,x:bs), (x:as,bs)] I think these functions are quite interesting, and I don't recall ever seeing them in any library. Have I discovered something new here, or am I reinventing the wheel? Anyway, I'm really loving the way the whole "list is a monad" concept allows you to write code like every variable is a superposition of all possible values... all_sums :: [Term] -> [Pick Term] all_sums ts = do (as,bs) <- picks ts if length as < 2 then fail "trivial sum" else return (Sum as, bs) all_negates :: [Term] -> [[Term]] all_negates [] = [[]] all_negates (t:ts) = do ts' <- all_negates ts [(t : ts'), (Negate t : ts')] Neat, eh?