What is Node in haskell?

What exactly is Node? is it a keyword? a data type? I can’t figure out how it works.

If if define this, for example

data Seq a = Empty | Node a (Seq a)

Am I saying there is a variable a with the type Node, am I defining a new type, what is it exactly?

>Solution :

In this case, Empty and Node are data constructors [Haskell wiki]. Each value with type Seq a is either an Empty, or a Node that wraps two parameters: the first one of type a, and the other one a Seq a value.

One can thus construct values with arbitrary size in this case, for example Empty, Node 1 Empty, Node 1 (Node 4 Empty), etc. Therefore you definition looks like the definition of a list [], which is implemented as a linked list in Haskell.

You can use data constructors as functions where they take parameters for the parameters, so Node can be used as a function Node :: a -> Seq a -> Seq a.

Data constructors are also used to pattern match. For example you can implement a function:

seqSize :: Seq a -> Int
seqSize Empty = 0
seqSize (Node _ xs) = 1 + seqSize xs

here it will thus pattern match and in case the value is an Empty it will return zero. For a Node the variable xs refers to the second parameter of the value (so also of type Seq a) that can then be used in the recursive call.