I now realize that my solution is needlessly complicated. Here's a simpler
one.
module Trees where
data Tree = Leaf Int | Branch Tree Tree
deriving (Show)
insert x t@(Leaf y) = [Branch s t, Branch t s] where s = Leaf x
insert x (Branch l r) = [Branch l' r | l' <- insert x l] ++
[Branch l r' | r' <- insert x r]
allTrees [] = []
allTrees (x:xs) = Leaf x : ts ++ [ s | t <- ts, s <- insert x t ]
where ts = allTrees xs
-- Lennart
On 6/13/07, Lennart Augustsson <[EMAIL PROTECTED]> wrote:
This doesn't enumerate them in the order you want, but maybe it doesn't
matter.
module Trees where
combinations :: [a] -> [[a]]
combinations [] = [[]]
combinations (x:xs)
= combinations xs ++ [ x:xs' | xs' <- combinations xs ]
data Tree = Leaf Int | Branch Tree Tree
deriving (Show)
trees [x] = [Leaf x]
trees (x:xs) = [ s | t <- trees xs, s <- insert x t ]
insert x t@(Leaf y) = [Branch s t, Branch t s] where s = Leaf x
insert x (Branch l r) = [Branch l' r | l' <- insert x l] ++
[Branch l r' | r' <- insert x r]
allTrees xs = [ t | ys <- combinations xs, not (null ys), t <- trees ys ]
-- Lennart
On 6/12/07, Andrew Coppin <[EMAIL PROTECTED]> wrote:
>
> I'm trying to construct a function
>
> all_trees :: [Int] -> [Tree]
>
> 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))
> ]
>
>
>
> So far I'm not doing too well. Here's what I've got:
>
> data Tree = Leaf Int | Branch Tree Tree
>
> pick :: [x] -> [(x,[x])]
> pick = pick_from []
>
> pick_from :: [x] -> [x] -> [(x,[x])]
> pick_from ks [] = []
> pick_from ks [x] = []
> pick_from ks xs = (head xs, ks ++ tail xs) : pick_from (ks ++ [head xs])
>
> (tail xs)
>
> setup :: [Int] -> [Tree]
> setup = map Leaf
>
> tree2 :: [Tree] -> [Tree]
> tree2 xs = do
> (x0,xs0) <- pick xs
> (x1,xs1) <- pick xs0
> return (Branch x0 x1)
>
> all_trees ns = (setup ns) ++ (tree2 $ setup ns)
>
> Clearly I need another layer of recursion here. (The input list is of
> arbitrary length.) However, I need to somehow avoid creating duplicate
> subtrees...
>
> (BTW, I'm really impressed with how useful the list monad is for
> constructing tree2...)
>
> _______________________________________________
> Haskell-Cafe mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
