[Haskell-cafe] Construct all possible trees

[Andrew Coppin]

Colin DeVilbiss wrote:
> On 6/12/07, Andrew Coppin <andrewcoppin at btinternet.com> wrote:
>
> Based on the sample output, I'm guessing that the desired output is
> "every tree which, when flattened, gives a permutation of a non-empty
> subset of the supplied list".  This limits the output to trees with up
> to "n" leaves.

Every possible tree, using the supplied elements as leaf elements, 
without ever duplicating them. (Note, however, that the initial list may 
contain duplicates in the first place, so you can't just test for and 
remove duplicates in the produced lists; you must avoid repeating 
elements by construction.)

>> Branch (Branch (Leaf 1) (Leaf 3)) (Leaf 1),
>
> If I'm guessing the desired output correctly, this must be a typo?

Erm... yes.

> I'd be tempted to solve the "list-only" problem first (generate all
> "sub-permutations" of a list), then solve the tree problem (generate
> all "un-flattenings" of a list).

I can already create all possible 2-element trees. It seems like there 
should be a way to recurse that... but without duplicating elements.

Hmm, I don't know - there's probably several correct solutions to this 
problem. ;-)