# Tree or not (Haskell type understanding)

• A+
Category：Languages

In "A Gentle Introduction to Haskell" we have such declaration of Tree's type:

``data Tree a = Leaf a | Branch (Tree a) (Tree a)      deriving (Eq,Ord,Show,Read) ``

Let's to make some values of this type:

``a1 = Leaf 1 a2 = Leaf 2 a3 = Leaf 3 a4 = a1 `Branch` a2 a5 = a2 `Branch` a3 a6 = a4 `Branch` a5 ``

in ghci:

``*Main> :t a6 a6 :: Tree Integer ``

But `a6` is not Tree at all, see:

``      a6      / /    a4   a5   / /  /  / a1   a2    a3 ``

There is a cycle in this graph! What is wrong? Is type definition of Tree correct? Or maybe, I can't catch some mistake in understanding of this example...

The short answer is that conceptually, `a2` "is" a `Tree a`, not a reference to a `Tree a`. In that sense, `a6` really looks like

``          a6        /      /      a4        a5     /   /    /    /   a1   a2   a2    a3 ``

that is, there are two "copies" of `a2` in the tree.

Practically speaking, since all the values are immutable, the implementation can use the same memory to represent both the right child of `a4` and the left child of `a5`, but the two nodes remain distinct at the level of abstraction represented by the `Tree a` type.

In order to actually have a cycle, there needs to be some notion of being able to reach both `a4` and `a5` from `a2`, and this type doesn't provide a representation for any such child-to-parent links, which makes it impossible to tell if `a4`'s left child and `a5`'s right child are the same node, or two different nodes that look exactly alike. For this data type, the distinction simply does not exist.