Introduction to Algebraic Data Types in Haskell
Constructor Functions vs Normal Functions
Constructor functions are the kinds of functions used to create types and values.
Constructor functions are different from normal functions in the sense that once they have had their arguments applied they are fully evaluated.
They have no equation or body so to speak. For example the value constructor Just 5 is a value just like 5 is except it has a different type.
Basic example of a custom type
Constructors are just functions
data Colour = RGB Int Int Int
RGB is a value constructor which is just a function of the type
Prelude> :t RGB
RGB :: Int -> Int -> Int -> Colour
So when we pass the construct function all is arguments we get back a value of type Colour
Prelude> :t RGB 5 5 5
RGB 5 5 5 :: Colour
Type Constructors vs Data Constructors
Type Constructors take zero or more types and return a new type
Data Constructors take zero or more values and return a new value
Data constructors that take no arguments are referred to as a constant value because it takes no arguments and stands only for itself. ( i.e the Nothing constant value from the Maybe type)
Type constructors take types and return types
Data constructors take values and return values
The difference between constructor functions and normal functions in haskell is that constructor functions have no defining equations when called are already fully evaluated. i.e
data Maybe a = Nothing | Just a
Once the type constructor is passed another type say Int we get
data Maybe Int = Nothing | Just Int
Now this type is evaluated fully i.e a concrete type (of kind *). The type Maybe and the and values one of which is called Nothing are just arbritary names.
These names are values that have no intrinsic meaning in haskell and could have been called anything. The important thing is that the name isn't already taken.
data Maybe Int = Nothing | Just Int
Above, Nothing is a data constructor that takes no arguments also called a nullary data constructor
Sum types vs product types
data Person = Person String Int
The type above is a product type since its data constructor takes two arguments.
The following type we just looked at is a sum type
data Maybe Int = Nothing | Just Int
The Nothing value constructor takes no arguments and the second value constructor called Just takes only one argument. Hence this type is a product type.
Kinds
Kinds are sets of types. Whereas Types are sets of values.
Concrete Types
Just like we can partially apply functions to get new functions, we can partially apply type parameters and get new type constructors from them.
Type constructors that take zero arguments are called Type Constants (concrete types *). A type constant or concrete type is one type whose constructor has been supplied with all its arguments or is nullary ( takes no arguments)
So we could supply a Bool type to Maybe as Bool is a concrete data type. Bool is a concrete type as it takes no arguments in its type constructor and is thus fully evaluated.
data Bool = True | False
Abstract Data Types
On the other hand abstract data types leaves some aspects of their structure undefined, to be provided by the user of the data type.
For example
Maybe a = Just a | Nothing
Is an abstract data type as the type constructor has not been supplied with a concrete type for its sole argument called 'a'
We can type :k in the interpreter to evaluate the kind of a type.
Lets look at the kind of the Maybe type constructor.
Prelude> :k Maybe
Maybe :: * -> *
So Maybe refers to a type constructor that takes a concrete (fully evaluated) type and returns another concrete type.
Maybe is not a concrete type so we couldn't supply a Maybe as an argument for its own type constructor
Prelude> :k Maybe Maybe
<interactive>:1:7:
Expecting one more argument to `Maybe'
In a type in a GHCi command: Maybe Maybe
So it is nonsensical to pass a type constructor to another type constructor
Once the Maybe type constructor is applied to a concrete type
Fully applied concrete types are represented as *
Maybe :: * -> *
Maybe Bool :: *