CODEWITHSUNDEEP
typesprogramming-languagessmlml
Tim
Tim

Reputation: 99408

What are the differences and relations between type constructors and datatypes?

In Ullman's SML book,

Questions:

  1. Are lists and option datatypes, type constructors, or both?

  2. What are the differences and relations between type constructors and datatypes? I am confused by the following quotes:

    Chapter 6 Defining Your Own Types says:

    Datatype definitions are rules for constructing new types with new values that are not the values of previously defined types.

    2.4 Tuples and Lists says:

    Most languages start with a similar collection of types and build more complex types with a set of operators called type constructors, which are dictions allowing us to define new types from simpler types.

  3. If type constructors and datatypes can overlap, what is the opposite (mutual exclusive) concept to type constructor and what is the opposite (mutual exclusive) concept to datatype?

Upvotes: 1

Views: 146

Answers (1)

sshine
sshine

Reputation: 16105

I hope this answer is sensible.

  1. list and option are both type constructors because they take a (prefix) type in order to construct a type. So int list is a type, but list itself is a type constructor. The same goes for option and int option, and so on.

    In Haskell and probably other type-oriented languages you would say that int option has kind Type while option has kind Type -> Type. Kinds are to types as types are to values, a means of saying things about all of them.

    So I believe that when you say "list is a type", this is loosely spoken. What you really mean is "α list is a type for any type α". And sometimes you specifically mean "'a list is a type" with 'a being a type variable. The difference being that by α I mean some concrete type and by 'a I mean some type variable.

  2. When you create a data type, datatype troolean = True | False | Derp, then troolean is a type and True, etc., are (nullary) value constructors.

    When you create a data type, datatype fiat = USD of int | ChildDrawing of png, then fiat is a type and Dollar is a value constructor with type int -> fiat.

    When you create a data type, datatype ('a, 'b) either = Left of 'a | Right of 'b, then ('a, 'b) either is a type, either is a type constructor (it takes two type parameters and constructs a type, but loosely spoken, "either is a type"), Left and Right are still value constructors.

    I'm not sure what confuses you about the quotes. Data types lets you create new types with new values that didn't exist (but the type most certainly is isomorphic to some type that existed). Composition of types is still possible, but even more powerful because you can compose types you made yourself for great precision and expressivity.

    I suppose you could call troolean a nullary type constructor, too, but it would probably be less confusing to say that troolean's kind is Type and that either's kind is... what?

  3. If type constructors and datatypes can overlap

    I'm not sure you can say that. Data types define new values. Sometimes those values have value parameters. Sometimes a data type itself has type parameters. When it does, its type constructor has a higher kind.

Upvotes: 2

Related Questions