[Haskell-cafe] Re: Construct all possible trees

[Mirko Rahn]

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/ ---