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/ ---
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
