[Haskell-cafe] All possible expressions [was All possible trees]

[Andrew Coppin]

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?