Generate All Possible Trees

Question

Given the following data type definition:

data FormTree = Empty | Node FormTree FormTree deriving Show

I want to write a function which generates an infinite list containing all possible trees sorted after length e.g. the amount of nodes.

The following code almost does what I need but it only descends the tree on the right side by inserting additional nodes every time but I need it to alternate between both sides.

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

Executing

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 nice trick, reminiscent of the standard Fibonacci numbers trick. We'll build a lazy list; each member of the list will be a list of all trees with a given number of nodes. There's just one tree with no nodes, Empty, and that will serve as our base case. To build all the trees with n nodes, we'll assume we already know how to build trees with 0, 1, 2, ..., n-1 nodes. Then we'll just non-deterministically choose a pairing of those that sums to n-1 and stuck 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 that's wanted. 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 do a quick sanity check:

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

...which is indeed the first ten Catalan numbers, so we probably got it right!