[Haskell-cafe] Construct all possible trees
Mirko Rahn
rahn at ira.uka.de
Wed Jun 13 07:45:44 EDT 2007
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/ ---
More information about the Haskell-Cafe
mailing list