[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/ ---
More information about the Haskell-Cafe
mailing list