[Haskell-beginners] Empty or Tree?

[Michael Schober]

> But when I try to create a more generic code like this which could work
> with trees who don't have empty nodes in grandchild level :
>
> function Node a (Node b Tree Tree) (Node c Tree Tree )

The problem is that 'Tree' is a type, not a constructor. Someone correct 
me, if I'm mistaken (this is my first post to the mailing-list, yieah 
:-)), but what seems to cause the problem is that the pattern matcher 
needs constructors, so it can determine, whether a pattern can produce 
an input data.

There are several solutions. If you don't need the further subtrees, 
leave them fully unspecified via the underscore:

function (Node a (Node b _ _) (Node c _ _)) = ...

or you could give them variable names like this:

function (Node a (Node b bl br) (Node c cl cr)) = ...

where bl, br, cl, and cr are variables of the type Tree. However, what 
you might want to accomplish is a recursive function over the recursive 
type to get a fully generic code. This usually looks something like this:

-- a generic recursive function
cFunction :: Tree -> a
cFunction Empty = ...
cFunction (Node i l r) = f i (cFunction l) (cFunction r)
   where
     f :: Integer -> a -> a -> a
     f int recLeft recRight = ...

Hope that helped.