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