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?
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
