Different binary tree's definitions in Haskell: which wins?

Question

I was used to the following Tree definition:

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

until I ran into this one somewhere:

data Tree a = Empty | Leaf a | Node a (Tree a) (Tree a)

which makes me wonder about Haskell idioms.

Since Leaf a is just Node a Empty Empty, should this constructor exist? We could remove Empty as well, using a unique constructor like

Tree (Maybe (a, (Tree a), (Tree a)))

or something like that.

The second definition I wrote is the "most expanded" one and the first is halfway between it and the last one. What's practically and theorically the best one? In other words, what about performance and data-types' design?

Answer 1

If you want idiomatic Haskell, use the first definition, because then you have less constructors to pattern-match against.

If you have huge binary trees with a lot of leaves, use the second definition if you want to save about 16 bytes (The extra Tree a-pointers) of memory per leaf (depends heavily on which platform/compiler you're using how much memory is saved).

The third alternative that you present is technically a valid representation (assuming that you meant Tree (Maybe (a, Tree a, Tree a)), but it is very tedious to work with.