[Haskell-cafe] Construct all possible trees

Mirko Rahn rahn at ira.uka.de
Thu Jun 14 02:31:45 EDT 2007

I'm afraid, but you are missing a case here. For example the tree

Branch (Leaf 1) (Branch (Leaf 3) (Leaf 2))

is not constructed by your program. Correct is

insert x t@(Leaf y) = [Branch s t, Branch t s]  where s = Leaf x
insert x t@(Branch l r) = [Branch l' r | l' <- insert x l] ++
                           [Branch l r' | r' <- insert x r] ++
        {- missed this: -} [Branch s t,Branch t s] where s = Leaf x

With this modification, your program becomes essentially the same as my 
version but with suboptimal sharing (you construct Leaf x twice and with 
the correction even three times). As a consequence my version is faster 
and eats less memory.


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

More information about the Haskell-Cafe mailing list