[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.
/BR
--
-- Mirko Rahn -- Tel +49-721 608 7504 --
--- http://liinwww.ira.uka.de/~rahn/ ---
More information about the Haskell-Cafe
mailing list