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
*Main> :t a6 a6 :: Tree Integer
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
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.