Create all possible trees

Question

Given the following data type definition:

data FormTree = Empty | Node FormTree FormTree deriving Show 

I want to write a function that generates an endless list containing all possible trees, sorted by length, for example. number of nodes.

The following code almost does what I need, but it only goes down the tree on the right, inserting additional nodes each time, but I need it to alternate between both sides.

 allPossibleTrees :: [FormTree] allPossibleTrees = Empty : [Node xy | x <- recursive, y <- recursive] where recursive = allPossibleTrees 

Performance

 take 5 allPossibleTrees 

gives:

 [Empty,Node Empty Empty,Node Empty (Node Empty Empty),Node Empty (Node Empty (Nodes Empty Empty)),Node Empty (Node Empty (Node Empty (Node Empty Empty)))] 

but it should be something like:

 [Empty,Node Empty Empty,Node (Node Empty Empty) Empty,Node Empty (Node Empty Empty),Node (Node Empty Empty) (Node Empty Empty)] 

Answer 1

Here's a good trick reminiscent of the standard Fibonacci trick. We will build a lazy list; each member of the list will be a list of all trees with a given number of nodes. There is only one tree with no nodes, Empty , and this will serve as our base case. To build all the trees with nodes n , suppose we already know how to build trees with nodes 0 , 1 , 2 , ..., n-1 . Then we just do not deterministically select the pairing of those that sums with n-1 , and glue a Node on top.

In code:

 import Control.Monad import Data.List sizes :: [[FormTree]] sizes = [Empty] : (map go . drop 1 . inits) sizes where go smaller = do (ls, rs) <- zip smaller (reverse smaller) liftM2 Node ls rs 

Then we can simply define allPossibleTrees = concat sizes , if necessary. The first few entries:

 *Main> mapM_ print (take 4 sizes) [Empty] [Node Empty Empty] [Node Empty (Node Empty Empty),Node (Node Empty Empty) Empty] [Node Empty (Node Empty (Node Empty Empty)),Node Empty (Node (Node Empty Empty) Empty),Node (Node Empty Empty) (Node Empty Empty),Node (Node Empty (Node Empty Empty)) Empty,Node (Node (Node Empty Empty) Empty) Empty] 

We can quickly check the performance:

 *Main> take 10 (map length sizes) [1,1,2,5,14,42,132,429,1430,4862] 

... these are really the first ten Catalan numbers , so we probably got it right!

Answer 2

List comprehension

 [ (x,y) | x<-[1..] , y<-[1..] ] 

begins with considering x=1 and constructing all pairs (1,y) for all possible y s. Then x=2 and all pairs (2,y) follow. etc.

However, there are infinitely many pairs (1,y) , so x=2 will be considered only after infinite time, that is, not at all.

Your code suffers from the same problem.

To see a possible solution, you can address this related issue using the Omega monad to achieve fair planning among all cases.

Answer 3

One way is to track the size of the tree (i.e. the number of Node constructors).

Suppose you had a function that returned trees using only n Node constructors:

 treesOfSize :: Int -> [FormTree] 

Then allTrees can be defined as:

 allTrees = concatMap treesOfSize [0..] 

The definition of treesOfSize can be recursively defined, and I'll let you know:

 treesOfSize 0 = [Empty] treesOfSize n = [ Node t1 t2 | ... ] 

Answer 4

control-monad-omega library seems to do the trick with your source code:

 {-# LANGUAGE MonadComprehensions #-} import Control.Monad.Omega data Empty = Empty | Node Empty Empty deriving Show allPossibleTrees :: [Empty] allPossibleTrees = Empty : runOmega [Node xy | x <- each allPossibleTrees, y <- each allPossibleTrees] 

The first 10 trees look good to me:

 *Main> mapM_ print $ take 10 allPossibleTrees Empty Node Empty Empty Node Empty (Node Empty Empty) Node (Node Empty Empty) Empty Node Empty (Node Empty (Node Empty Empty)) Node (Node Empty Empty) (Node Empty Empty) Node (Node Empty (Node Empty Empty)) Empty Node Empty (Node (Node Empty Empty) Empty) Node (Node Empty Empty) (Node Empty (Node Empty Empty)) Node (Node Empty (Node Empty Empty)) (Node Empty Empty)