[Haskell-cafe] Re: Construct all possible trees

[Mirko Rahn]

apfelmus wrote:

Explanation and the code:

>     import Data.List
>     import Control.Applicative
>     import qualified Data.Foldable as Foldable
>     import Data.Traversable as Traversable
>     import Control.Monad.State
> 
>     data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving (Show)

>     instance Traversable Tree where
>         traverse f (Leaf a)     = Leaf <$> f a
>         traverse f (Branch x y) =
>            Branch <$> traverse f x <*> traverse f y
> 
>     instance Functor Tree where
>         fmap = fmapDefault
> 
>     instance Foldable.Foldable Tree where
>         foldMap = foldMapDefault

>     permTrees xs = concat . takeWhile (not . null) . map
>         (flip evalStateT xs . Traversable.sequence) $ trees select
>         where
>         select = StateT $ \xs ->
>             [(z,ys++zs) | (ys,z:zs) <- zip (inits xs) (tails xs)]

>     trees x = ts
>         where ts = concat $ ([Leaf x] :) $ convolution Branch ts ts

>     convolution f xs ys = tail $
>         zipWith (zipWith f) (inits' xs) $ scanl (flip (:)) [] ys

>     inits' xs = []:case xs of
>         []     -> []
>         (x:xs) -> map (x:) $ inits' xs

But something is wrong here. Unfortunately, I cannot say what, but for 
example the following trees are missing in permTrees [1,2,3,4]:

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

One could guess it has something to do with the special structure of the 
missing trees, but at one hand permTrees [1,2,3] gives all trees and at 
the other in permTrees [1,2,3,4,5] are also other structures missing, like

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

So please, what's going on here?

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