Type constructors and type constants (and type variables): What's the difference?

Question

I got confused about the difference between type constructors, type constants, and type variables.

A Haskell 98 report says there are 4 types of type expressions:

• Enter variables
• Type constructors
• Enter application
• Type of brackets

So what is a type constant? The report says: "Char, Int ... are type constants," but I cannot find a more detailed example. Even more confusing is that IO first called a “unitary type constructor”, but then called a “constant, IO”.

The reason I ask is because it is a document for implementing a system like Haskell . It says the following:

Haskell-type expressions are either type variables or constants (each of which has a related form) or applications of one type to another: applying a type of the form k1 → k2 to a type of the type k1 gives a type of the type k2

He says something other than a report. Are the second type of expressions like "constructors" or "constants"?

The document also contains code showing the view:

 data Type = TVar Tyvar | TCon Tycon | TAp Type Type | TGen Int deriving Eq data Tyvar = Tyvar Id Kind deriving Eq data Tycon = Tycon Id Kind deriving Eq 

Tycon mean "type constructor," but then what does TCon mean? What about Tyvar and TVar ? Why is there a need to separate T and Ty ?

Answer 1

Last question

Tycon seems to mean "type constructor," but then what is TCon? What about Tiwara and TVar? Why is there a need to separate T and Ty?

the first.

"T" in TCon , TVar , etc. is just a marker that refers to types and that they are Type constructors. TCon takes a value of type Tycon and builds a value of type Type from this, etc. The Type constructor does not have the Ty prefix, but most likely T , to avoid confusion, the type could be defined

 data Type = Tyvar Tyvar | Tycon Tycon | ... 

since constructors and value types live in different namespaces, but this could open the way for more confusion.

1 type variables

- these are expressions of the type that can be replaced by expressions of another type, their identifiers begin with lowercase letters (or they can be characters that do not begin with: :).

2 Type Constructors

are type expressions that take zero or more arguments of a type expression to construct a type of type * , for example

• Int
• Char
• Twice

are constructors with a null type, they take the arguments of an expression of a null type to construct a type of the form * , these are also type constants.

• May be,
• IO
• []

are unitary type constructors; they take one type expression ( * type in these examples, but unitary type constructors can accept other types of arguments).

• Or
• ()

- constructors of binary type,

• Statet

is a three-dimensional type constructor that has two arguments of the form * and one of the types * -> * (thus StateT StateT :: * -> (* -> *) -> * -> * ).

3 Type of application

is an expression of the type of the form t1 t2 . It is only well formed if t2 has the form k2 , and t1 has the form k2 -> k3 (similar to applying the function). For example, StateT s is a type application, an expression of type StateT is applied to a variable of type s .

4 Type of brackets

- this is an expression of type in parentheses, which may be required for resolution or parsing of priority, otherwise it will be the same as an expression without an indirect type, for example, in

 instance Monad (Either e) where ... 

an expression in brackets of type (Either e) matches Either e , but parentheses are needed to distinguish it from an instance of a two-parameter class for two expressions of type Either and e . In type

 StateT s ((->) a) b 

parentheses around (->) a are for evaluation. (Note that the type constructor (->) is a special case not covered by the general rule that type constructors begin with uppercase letters like [] , (,) , (,,) , etc.)

Now enter the constants. These are simply type expressions that do not contain type variables, but I don't think it is formally defined anywhere. Thus, any type expression with only uppercase identifiers (including characters starting with ":") and special cases ( [] , (->) , (,) , ...) is a type constant.

• expressions of the type of one token starting with an uppercase letter (':' for characters), or special cases are type constants
• a type expression consisting entirely of type constants is a type constant

Answer 2

In type theory, a “type constructor" usually refers to a type expression of a higher type. In prevalence, simple types are often included as a degenerate case.

In programming languages, a "type constructor" is often used with a more specific meaning, referring to named type constructors that are defined by context. Again, this may include simple types as a degenerate case with null parameters.

The term "type constant" is somewhat less standard. In the Haskell definition, it appears to be used informally and is probably intended to refer to a subset of named type constructors that are predefined by the language (unlike custom type constructors, which are defined in terms of algebraic types and predefined type constructors). Therefore, each constant is also a type constructor.

As for “T” and “Ty,” it just looks like a naming convention in the code snippet you're looking at, designed to differentiate between language level data constructors (“T”) and language level type constructors (“Ty”). The reason he defines Tycon and Tyvar in the definitions of individual types is probably because they are used separately by some code fragments.

Answer 3

Are the second type of expressions like "constructors" or "constants"?

There is no reason for confusion.

Let's see, we can say that 5 is a constructor of values, because it builds the value of 5. And at the same time, we can say that 5 is a constant.

Another example: in the Maybe type we have

 data Maybe a = Just a | Nothing 

Both Just and Nothing are value constructors. It's easy to see that Nothing also a constant. It may be more difficult to understand that Just also a constant: it denotes a function that, for any value, creates a value of type Maybe . If you find this difficult to understand, imagine that machine code will be used in program memory using Just , which actually performs the task of constructing Maybe values. This code never changes, therefore it is constant, and Just is how we refer to this constant.

Now we understand what a constant and a constructor mean in the range of values, we can extend this to the type range.