# [Haskell-cafe] Re: Construct all possible trees

Mirko Rahn rahn at ira.uka.de
Thu Jun 14 03:40:08 EDT 2007

```Jon Fairbairn wrote:

> Trees with all the elements of a list in that order:

>>the_trees [x] = [Leaf x]
>>the_trees l = zipWith Branch (concat (map the_trees (tail \$ inits l)))
>>                             (concat (map the_trees (tail \$ tails l)))

Sorry, but this problem seems to trigger incorrect codes, somehow.

Here we have the_trees [1,2,3,4] outputs

Branch (Leaf 1) (Branch (Leaf 2) (Branch (Leaf 3) (Leaf 4)))
Branch (Branch (Leaf 1) (Leaf 2))
(Branch (Branch (Leaf 2) (Leaf 3)) (Leaf 4))
Branch (Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3)))
(Branch (Leaf 3) (Leaf 4))
Branch (Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3)) (Leaf 4)

which is certainly not as wanted. The problem is that you do the concat
before the zip. We have for

splits xs = zip (tail . inits \$ xs) (tail . tails \$ xs)

splits [1,2,3,4] == ([1],[2,3,4]) : ([1,2],[3,4]) : ...

So now

length (the_trees [1]    ) == 1
length (the_trees [1,2]  ) == 1
length (the_trees [2,3,4]) == 2

So we build a Branch from the first tree with labels [1,2] and the last
tree with labels [2,3,4]. That's wrong!

A fixed version could look like

the_trees [x] = [Leaf x]
the_trees xs  = nonempty_splits xs >>= \ (l,r) ->
[ Branch a b | a <- the_trees l, b <- the_trees r ]

nonempty_splits (x:y:ys) = ([x],y:ys)
: [ (x:l,r) | (l,r) <- nonempty_splits (y:ys) ]
nonempty_splits _        = []

/BR

--
-- Mirko Rahn -- Tel +49-721 608 7504 --
--- http://liinwww.ira.uka.de/~rahn/ ---
```