- A+

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.