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/ ---
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe