Different definitions of a binary tree in Haskell: what benefits?

Question

I used the following Tree definition:

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

until I came across this:

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

which makes me think about Haskell icons.

Since Leaf a is just Node a Empty Empty , should this constructor exist? We could remove Empty using a unique constructor, for example

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

or something like that.

The second definition that I wrote is "the most extended," and the first is halfway between it and the last. Which is practically and theoretically the best? In other words, what about performance design and data types?

Answer 1

If you need an idiomatic Haskell, use the first definition, because then you have fewer constructors for pattern matching.

If you have huge binary trees with a lot of leaves, use the second definition if you want to save about 16 bytes (additional Tree a -pointers) of memory per sheet (it depends very much on which platform / re using the amount of memory).

The third option that you present is a technically feasible representation (assuming you mean Tree (Maybe (a, Tree a, Tree a)) , but working with it is very tedious.

Answer 2

The dflemstr answer is in place, but I thought I would add two comments (which may not be satisfied with the comment on the original answer).

Firstly, by the same logic that the second definition can save memory, a similar argument can be made for this:

 data Tree a = Empty | Leaf a | LeftOnly a (Tree a) | RightOnly a (Tree a) | Branch a (Tree a) (Tree a) 

It doesn't matter if it depends on your application.

A second and more important point is that if you avoid using data constructors directly, you can ignore these implementations. For example, equivalent foldTree functions can be written for any of these types. For a shorter type, you do it like this:

 data Tree a = Empty | Node a (Tree a) (Tree a) foldTree :: (a -> b -> b -> b) -> b -> Tree a -> b foldTree fz Empty = z foldTree fz (Node vlr) = fv (subfold l) (subfold r) where subfold = foldTree fz 

And for a longer one, you can write this as follows:

 data Tree a = Empty | Leaf a | Node a (Tree a) (Tree a) foldTree :: (a -> b -> b -> b) -> b -> Tree a -> b foldTree fz Empty = z foldTree fz (Leaf v) = fvzz foldTree fz (Node vlr) = fv (subfold l) (subfold r) where subfold = foldTree fz 

The same can be done for your Maybe alternative or for my alternative with five constructors. In addition, this method can be applied to all other common tree functions that you need. (In fact, many of these functions can be written in foldTree terms, so most of them fall foldTree definitions above.)