What is Node in haskell?

Question

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?

Answer 1

As the comment states, Node is a data constructor. This means it's a possible way of constructing a value of type Seq a (where a represents another type).

This particular data structure represents a sequence, which can be constructed either using the Empty data constructor or with the Node one.

For example:

empty :: Seq a
empty = Empty

seqOf1Int :: Seq Int
seqOf1Int = Node 5 Empty

seqOf2Strings :: Seq String
seqOf2Strings = Node "hello" (Node "world" Empty)

Answer 2

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.

Answer 3

In general, Node is an identifier starting with a capital letter, which means that it's a valid name for type and data constructors.

In this specific code you're defining it as a data constructor that takes two arguments of types a and Seq a respectively and which belongs to the type Seq a.

Answer 4

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

is a data type definition where Seq a is the type and Empty and Node a (Seq a) are its constructors.

Node is a recursive constructor. It has a value of type a that it receives as a parameter on construction. The second parameter to Node is of type Seq a which is the type of Node itself, thus it becomes a recursive data structure. Seq a that is passed as a parameter to Node can be constructed with any of Seqs constructors, namely Empty and Node. Empty closes the recursive data structure as it doesn't receive itself any new parameters of type Seq a.