How to use constructors correctly when writing structures and what are the alternatives to Null?-CodePudding

I'm trying to write a red-black tree in haskell. In the properties of the red-black tree there is a note that all leaves that do not contain data are black.

I want to write something like this:

data EmptyNode = EmptyNode{
data = ???,
color = ???,  <-- it should black (assume that it is False)
left = ???, 
right = ???
}
data NodeBR a = NodeBR {
  data :: a,
  color :: Bool,
  left :: NodeBR,
  right :: NodeBR
} 

data TreeBR a = EmptyNode | NodeBR a (TreeBR a) (TreeBR a)

I don't understand 2 things, what type is suitable for me to replace Null in the usual languages (undefined as I understand you can not use here) and work with constructors, how can I specify color in EmptyNode defaults to False?

CodePudding user response：

One solution is to define the red-black tree (RBT for short) in a more "Haskell" way. So there are two possible ways to construct an RBT:

Leaf (EmptyNode in your code)
Node a c l r (NodeBR in your code), where a is the data, c is the color, l and r are also RBT.

data RBT a = Leaf | Node a Bool (RBT a) (RBT a)

In the line above, we have defined datatype RBT a with two constructors:

Leaf :: RBT a
Node :: a -> Bool -> RBT a -> RBT a -> RBT a

which means:

Leaf is of type RBT a
Node is a function, taking a, Bool(color), RBT a (left tree), RBT a (right tree), which returns an RBT a.

Therefore, we don't need to specify NULL in this case for Leaf, as there is no need for saying so at all (i.e., with Leaf, we want to say there is no data, no left/right subtree).

To treat Leaf as black, we could define a function on RBT a using pattern matching:

color :: RBT a -> Bool
color Leaf = False
color (Node _ c _ _) = c

The record syntax which you have mentioned in your code is just syntactic sugar for generating such color function. But in this case, using record syntax cannot generate the correct code for the Leaf case, as they are not identical in the declaration.

Thus, when you have to check if an RBT a is Leaf or not, you can just use pattern matching instead of "if-with-null" in other languages.