Recursive data types in haskell

Question

Consider the following definition taken from a textbook at http://www.haskell.org :

data Tree a = Leaf a | Branch (Tree a) (Tree a) fringe :: Tree a -> [a] fringe (Leaf x) = [x] fringe (Branch left right) = fringe left ++ fringe right 

I do not understand what happens at runtime when the fringe function is executed.

When compiling the expression fringe left , (1) the compiler somehow already knows whether the tree is a left Branch or a Leaf - that is, it works only on statically known trees - or (2) emits some if / switch conditions to check whether the tree is a left Leaf or Branch

If this is later ie (2), then why should it be more typical than the equivalent C function, which would basically look the same as above, except that there is only one type floating around (pointer to node )

Answer 1

It:

 fringe (Leaf x) = [x] fringe (Branch left right) = fringe left ++ fringe right 

exactly equivalent to the function of one variable, which immediately matches the pattern:

 fringe t = case t of Leaf x -> [x] Branch left right -> fringe left ++ fringe right 

So this answers your first question like (2): "it emits [s] some case conditions to check if the left tree is a Leaf or Branch ."

As for why this is safer than what you would do in C, well, what would you do in C?

Usually you end up storing a tag product that shows that something is a Leaf or Branch , and a payload that is an unlabeled union of a and (Tree a, Tree a) . Then the code you write matches the lines of the following (which is probably not 100% legal C, but should get a point):

 enum TreeTag { Tree_Leaf; Tree_Branch; }; struct Tree { TreeTag tag; union payload { struct { int x; // yeah let not touch on parametric polymorphism here... } Leaf; struct { Tree l; Tree r; } Branch; }; }; switch (t.tag) { case Tree_Leaf: ... use t.payload.Leaf.x here case Tree_Branch: ... use t.payload.Branch.left and t.payload.Branch.right here } 

The problem is that there is nothing static preventing the accidental use of t.payload.Branch.left in case of Tree_Leaf etc. Also, there is nothing static for you to do something like

 t.tag = Tree_Branch; t.payload.Leaf.x = 42; 

which will result in an invalid "type" Tree value.