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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: