[Haskell-cafe] Construct all possible trees

[Mirko Rahn]

Andrew Coppin wrote:

> such that all_trees [1,2,3] will yield

> [
> Leaf 1,
> Leaf 2,
> Leaf 3,
> Branch (Leaf 1) (Leaf 2),
> Branch (Leaf 1) (Leaf 3),
> Branch (Leaf 2) (Leaf 1),
> Branch (Leaf 2) (Leaf 3),
> Branch (Leaf 3) (Leaf 1),
> Branch (Leaf 3) (Leaf 2),
> Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3),
> Branch (Branch (Leaf 1) (Leaf 3)) (Leaf 1),
> Branch (Branch (Leaf 2) (Leaf 1)) (Leaf 3),
> Branch (Branch (Leaf 2) (Leaf 3)) (Leaf 1),
> Branch (Branch (Leaf 3) (Leaf 1)) (Leaf 2),
> Branch (Branch (Leaf 3) (Leaf 2)) (Leaf 1),
> Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3)),
> Branch (Leaf 1) (Branch (Leaf 3) (Leaf 2)),
> Branch (Leaf 2) (Branch (Leaf 1) (Leaf 3)),
> Branch (Leaf 2) (Branch (Leaf 3) (Leaf 2)),
> Branch (Leaf 3) (Branch (Leaf 1) (Leaf 2)),
> Branch (Leaf 3) (Branch (Leaf 2) (Leaf 1))
> ]

Just another way (assuming the given order is not relevant), based on 
the idea that it is quite easy to insert a new node on all possible 
positions in an already existing tree.

data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving Show

decomp (Branch l r) = [(l,flip Branch r),(r,Branch l)]
decomp _            = []

insert x t = Branch x t
            : Branch t x
            : [re b | (part,re) <- decomp t, b <- insert x part]

all_trees []     = []
all_trees (x:xs) =
     let this = Leaf x
         more = all_trees xs
     in this : more ++ concatMap (insert this) more

/BR

-- 
-- Mirko Rahn -- Tel +49-721 608 7504 --
--- http://liinwww.ira.uka.de/~rahn/ ---