I need to create haskell function, which returns all possible binary trees, given a list of integers

Question

As the title says, I need this:

    getAllTrees :: [Int] -> [Tree Int]
    getAllTrees xs = undefined

where tree is

    data Tree x 
      = Null
      | Leaf x
      | Node (Tree x) x (Tree x)

I will appreciate any help, even the smallest clue :) Thanks

Answer 1

I usually find it easiest to use the list monad for these kinds of problems. We can define getAllTrees by reasoning as follows:

The only tree of zero items is Null:

getAllTrees [] = return Null

There is also only one tree of one element, namely a Leaf:

getAllTrees [x] = return $ Leaf x

When we have more than one element, we can split the list in all possible ways to determine how we should branch, and then recursively generate the sub-trees from each list. Let's say we have a function splits :: [a] -> [([a], [a])] that returns all ways of splitting a list, for example:

> splits [1..3]
[([],[1,2,3]),([1],[2,3]),([1,2],[3]),([1,2,3],[])]

We can then define the final case of getAllTrees by using the list monad. This allows us to write code which sort of looks like like we're focusing on only one case, and the monad will give us all the combinations.

getAllTrees xs = do
  (left, x : right) <- splits xs
  Node <$> getAllTrees left <*> pure x <*> getAllTrees right

The first line splits the input list and takes the first item from the second part as the middle element. The case when the second part is empty doesn't match the pattern, so it gets discarded since that's how the list monad handles pattern match failures.

The second line uses applicative syntax to say that we want the result to be a list of nodes, made from all combinations of sub-trees from the left list, the fixed middle element x, and all sub-trees from the right list.

All that remains then is to implement splits. Looking at the example above, it's easy to see that we can just take the inits and tails of the list and zip them together:

splits xs = zip (inits xs) (tails xs)

Time for a quick sanity check in the interpreter:

> mapM_ print $ getAllTrees [1..3]
Node Null 1 (Node Null 2 (Leaf 3))
Node Null 1 (Node (Leaf 2) 3 Null)
Node (Leaf 1) 2 (Leaf 3)
Node (Node Null 1 (Leaf 2)) 3 Null
Node (Node (Leaf 1) 2 Null) 3 Null
> length $ getAllTrees [1..5]
42

Looks like we're done! Some key lessons:

• Try to think about the small cases first, and build up from there.
• The list monad is useful for code that needs to generate all combinations of things.
• You don't have to do everything at once. Dealing with the list splitting separately made the code much simpler than it would have been otherwise.