How should I define a binary tree in Haskell?

Question

In Haskell, a binary tree can be defined in either of the two ways:

data Tree a = Empty | Branch a (Tree a) (Tree a)

or

data Tree a = Leaf a | Branch (Tree a) (Tree a)

What are the advantages of choosing one over the other? In which situations is one tree structure a better suit over the other?

Answer 1

It largely depends on your application. The former definition is better if the shape of the tree is determined by the elements, for example if you have a balanced binary tree:

On the other hand, if your tree acts as a container for unconstrained elements where the shape of the tree doesn't depend on them, it makes more sense to put the values to the leaves.

This post by Heinrich Apfelmus shows very nicely such an approach. He defines

data Tree v a = Leaf   v a
              | Branch v (Tree v a) (Tree v a)

So values of type a are just at leaves, but all nodes (both internal and leaves) are annotated by type v, and just by choosing various monoids for v, we get different interesting data structures.

Answer 2

As @PetrPudlák says, it depends. The former is better for search trees. However, the latter version is a (free) monad, which can also be useful:

instance Monad Tree where
    return = Leaf
    Leaf x >>= f = f x
    Branch t1 t2 >>= f = Branch (t1 >>= f) (t2 >>= f)

The (>>=) operator corresponds to "substitution at the leaves".

The Functor and Applicative instances are useful as well. With GHC 7.10 out they have become mandatory when you define Monad. We can use monad functions to define them:

instance Functor Tree where fmap = Control.Monad.liftM
instance Applicative Tree where pure = return; (<*>) = Control.Monad.ap