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

Andrew Coppin andrewcoppin at btinternet.com
Fri Jun 15 16:44:43 EDT 2007

```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?

```