Trees in Haskell

Question

Still learning haskell, and I cannot really see the difference between

data Tree a = Leaf a | Branch [Tree a]

and

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

What is best according to you? What is the implication of these two ways of writing ?

Solution 1

The branch of the first one holds a list of Trees, so potentially any number of subtrees. The 2nd is explicitly two subtrees, thus a binary tree.

Solution 2

The former defines a tree where each branch can have arbitrarily many subtrees (represented as a list of trees) and the latter defines a tree where each branch has exactly two subtrees.

In other words the former is a general tree and the latter is a binary tree.

So which one to choose depends on whether you want to model a general tree or a binary tree.

Solution 3

I've put this as an answer rather than comment so it have some formatting:

data Rose a = Branch a [Rose a]
  deriving (Show)
sample1 :: Rose Int
sample1 = Branch 1 [Branch 2 [], Branch 3 [Branch 5 []], Branch 4 []]

This is the same as the library module Data.Tree, although Data.Tree uses field-labels and a type synonym.

I've seen both this tree and your first definition called "Rose trees" although they have slightly different shapes so the terminology doesn't seem to be entirely precise. My interpretation is that it is the list "[Rose a]" embedded in the single recursive constructor that is defining it as a Rose tree.

Comments

[Stephane Rolland]

Okay, but in both case Leaf and Branch are defined by the language, and I define my own type Tree. isn't it ?

[sepp2k]

@Stephane: No. In both cases neither the type Tree nor the constructors Leaf and Branch existed previously, and you're defining all three of them with your data definition.

[stephen tetley]

Hi sepp2k - the "general tree" defined in the question is more usually called a rose tree. Sometimes they are implemented with a separate Leaf constructor as above - sometimes as per Data.Tree the Branch constructor carries the data instead.

[Stephane Rolland]

@Stephen, could you write down the definition of the other implementation of the rose tree you are referring to ?