I now realize that my solution is needlessly complicated. Here's a simpler one.<br><br>module Trees where<br><br>data Tree = Leaf Int | Branch Tree Tree<br> deriving (Show)<br><br>insert x t@(Leaf y) = [Branch s t, Branch t s] where s = Leaf x
<br>insert x (Branch l r) = [Branch l' r | l' <- insert x l] ++<br> [Branch l r' | r' <- insert x r]<br><br>allTrees [] = []<br>allTrees (x:xs) = Leaf x : ts ++ [ s | t <- ts, s <- insert x t ]
<br> where ts = allTrees xs<br><br> -- Lennart<br><br><br><div><span class="gmail_quote">On 6/13/07, <b class="gmail_sendername">Lennart Augustsson</b> <<a href="mailto:lennart@augustsson.net">lennart@augustsson.net</a>
> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">This doesn't enumerate them in the order you want, but maybe it doesn't matter.
<br><br>module Trees where<br><br>combinations :: [a] -> [[a]]<br>combinations [] = [[]]<br>combinations (x:xs)<br> = combinations xs ++ [ x:xs' | xs' <- combinations xs ]
<span class="q"><br><br>data Tree = Leaf Int | Branch Tree Tree<br></span> deriving (Show)<br><br>trees [x] = [Leaf x]<br>trees (x:xs) = [ s | t <- trees xs, s <- insert x t ]<br><br>insert x t@(Leaf y) = [Branch s t, Branch t s] where s = Leaf x
<br>insert x (Branch l r) = [Branch l' r | l' <- insert x l] ++<br> [Branch l r' | r' <- insert x r]<br><br>allTrees xs = [ t | ys <- combinations xs, not (null ys), t <- trees ys ]
<br><span class="sg"><br> -- Lennart<br><br><br></span><div><span class="q"><span class="gmail_quote">On 6/12/07, <b class="gmail_sendername">Andrew Coppin</b> <<a href="mailto:andrewcoppin@btinternet.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">
andrewcoppin@btinternet.com</a>> wrote:</span></span><div><span class="e" id="q_11326eaa4c95458f_6"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
I'm trying to construct a function<br><br> all_trees :: [Int] -> [Tree]<br><br>such that all_trees [1,2,3] will yield<br><br>[<br>Leaf 1,<br>Leaf 2,<br>Leaf 3,<br>Branch (Leaf 1) (Leaf 2),<br>Branch (Leaf 1) (Leaf 3),
<br>Branch (Leaf 2) (Leaf 1),<br>Branch (Leaf 2) (Leaf 3),<br>Branch (Leaf 3) (Leaf 1),<br>Branch (Leaf 3) (Leaf 2),<br>Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3),<br>Branch (Branch (Leaf 1) (Leaf 3)) (Leaf 1),<br>Branch (Branch (Leaf 2) (Leaf 1)) (Leaf 3),
<br>Branch (Branch (Leaf 2) (Leaf 3)) (Leaf 1),<br>Branch (Branch (Leaf 3) (Leaf 1)) (Leaf 2),<br>Branch (Branch (Leaf 3) (Leaf 2)) (Leaf 1),<br>Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3)),<br>Branch (Leaf 1) (Branch (Leaf 3) (Leaf 2)),
<br>Branch (Leaf 2) (Branch (Leaf 1) (Leaf 3)),<br>Branch (Leaf 2) (Branch (Leaf 3) (Leaf 2)),<br>Branch (Leaf 3) (Branch (Leaf 1) (Leaf 2)),<br>Branch (Leaf 3) (Branch (Leaf 2) (Leaf 1))<br>]<br><br><br><br>So far I'm not doing too well. Here's what I've got:
<br><br>data Tree = Leaf Int | Branch Tree Tree<br><br>pick :: [x] -> [(x,[x])]<br>pick = pick_from []<br><br>pick_from :: [x] -> [x] -> [(x,[x])]<br>pick_from ks [] = []<br>pick_from ks [x] = []<br>pick_from ks xs = (head xs, ks ++ tail xs) : pick_from (ks ++ [head xs])
<br>(tail xs)<br><br>setup :: [Int] -> [Tree]<br>setup = map Leaf<br><br>tree2 :: [Tree] -> [Tree]<br>tree2 xs = do<br> (x0,xs0) <- pick xs<br> (x1,xs1) <- pick xs0<br> return (Branch x0 x1)<br><br>all_trees ns = (setup ns) ++ (tree2 $ setup ns)
<br><br>Clearly I need another layer of recursion here. (The input list is of<br>arbitrary length.) However, I need to somehow avoid creating duplicate<br>subtrees...<br><br>(BTW, I'm really impressed with how useful the list monad is for
<br>constructing tree2...)<br><br>_______________________________________________<br>Haskell-Cafe mailing list<br><a href="mailto:Haskell-Cafe@haskell.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">
Haskell-Cafe@haskell.org</a><br><a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">
http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br></blockquote></span></div></div><br>
</blockquote></div><br>