Question

4. For each of the following haskell type declarations, declare an object of the type this. a. type this = ([Bool], Float) b. type this = (Float, Integer) -> ([Float], Integer) c. data that = new Char | old Integer type this = [(Float, that)] d. type this = (a, b) -> (a, a)

Answer 1

Haskell is a purely functional language, all computations are done via the evaluation of expressions (syntactic terms) to yield values (abstract entities that we regard as answers). Every value has an associated type. (Intuitively, we can think of types as sets of values.) Examples of expressions include atomic values such as the integer 5, the character 'a', and the function \x -> x+1, as well as structured values such as the list [1,2,3] and the pair ('b',4).

Just as expressions denote values, type expressions are syntactic terms that denote type values (or just types). Examples of type expressions include the atomic types Integer (infinite-precision integers), Char (characters), Integer->Integer (functions mapping Integer to Integer), as well as the structured types [Integer] (homogeneous lists of integers) and (Char,Integer) (character, integer pairs).

All Haskell values are "first-class"---they may be passed as arguments to functions, returned as results, placed in data structures, etc. Haskell types, on the other hand, are not first-class. Types in a sense describe values, and the association of a value with its type is called a typing. Using the examples of values and types above, we write typings as follows:

5 :: Integer
'a' :: Char
inc :: Integer -> Integer
[1,2,3] :: [Integer]
('b',4) :: (Char,Integer)

The "::" can be read "has type."

Functions in Haskell are normally defined by a series of equations. For example, the function inc can be defined by the single equation:

inc n = n+1

An equation is an example of a declaration. Another kind of declaration is a type signature declaration (§4.4.1), with which we can declare an explicit typing for inc:

inc :: Integer -> Integer

For pedagogical purposes, when we wish to indicate that an expression e1 evaluates, or "reduces," to another expression or value e2, we will write:

e1 => e2

For example, note that:

inc (inc 3) => 5

Haskell's static type system defines the formal relationship between types and values (§4.1.4). The static type system ensures that Haskell programs are type safe; that is, that the programmer has not mismatched types in some way. For example, we cannot generally add together two characters, so the expression 'a'+'b' is ill-typed. The main advantage of statically typed languages is well-known: All type errors are detected at compile-time. Not all errors are caught by the type system; an expression such as 1/0 is typable but its evaluation will result in an error at execution time. Still, the type system finds many program errors at compile time, aids the user in reasoning about programs, and also permits a compiler to generate more efficient code (for example, no run-time type tags or tests are required).

Haskell type expressions

Syntax of Types

type   →   btype [-> type]   (function type)

btype   →   [btype] atype   (type application)

atype   →   gtycon
|   tyvar
|   ( type1 , … , typek )   (tuple type, k ≥ 2)
|   [ type ]   (list type)
|   ( type )   (parenthesised constructor)

gtycon   →   qtycon
|   ()   (unit type)
|   []   (list constructor)
|   (->)   (function constructor)
|   (,{,})   (tupling constructors)

The type system also ensures that user-supplied type signatures are correct. In fact, Haskell's type system is powerful enough to allow us to avoid writing any type signatures at all; (With a few exceptions to be described later.) we say that the type system infers the correct types for us. Nevertheless, judicious placement of type signatures such as that we gave for inc is a good idea, since type signatures are a very effective form of documentation and help bring programming errors to light.

Polymorphic Types

Haskell also incorporates polymorphic types---types that are universally quantified in some way over all types. Polymorphic type expressions essentially describe families of types. For example, (forall a)[a] is the family of types consisting of, for every type a, the type of lists of a. Lists of integers (e.g. [1,2,3]), lists of characters (['a','b','c']), even lists of lists of integers, etc., are all members of this family. (Note, however, that [2,'b'] is not a valid example, since there is no single type that contains both 2 and 'b'.)

Lists are a commonly used data structure in functional languages, and are a good vehicle for explaining the principles of polymorphism. The list [1,2,3] in Haskell is actually shorthand for the list 1:(2:(3:[])), where [] is the empty list and : is the infix operator that adds its first argument to the front of its second argument (a list). (: and [] are like Lisp's cons and nil, respectively.) Since : is right associative, we can also write this list as 1:2:3:[].

User-Defined Types

We can define our own types in Haskell using a data declaration, which we introduce via a series of examples (§4.2.1).

An important predefined type in Haskell is that of truth values:

data Bool = False | True

The type being defined here is Bool, and it has exactly two values: True and False. Type Bool is an example of a (nullary) type constructor, and True and False are (also nullary) data constructors (or just constructors, for short).

Similarly, we might wish to define a color type:

data Color = Red | Green | Blue | Indigo | Violet

Both Bool and Color are examples of enumerated types, since they consist of a finite number of nullary data constructors.

Here is an example of a type with just one data constructor:

data Point a = Pt a a

Because of the single constructor, a type like Point is often called a tuple type, since it is essentially just a cartesian product (in this case binary) of other types. (Tuples are somewhat like records in other languages.) In contrast, multi-constructor types, such as Bool and Color, are called (disjoint) union or sum types.

Note that the type of the binary data constructor Pt is a -> a -> Point a, and thus the following typings are valid:

Pt 2.0 3.0 :: Point Float
Pt 'a' 'b' :: Point Char
Pt True False :: Point Bool

On the other hand, an expression such as Pt 'a' 1 is ill-typed because 'a' and 1 are of different types.

It is important to distinguish between applying a data constructor to yield a value, and applying a type constructor to yield a type; the former happens at run-time and is how we compute things in Haskell, whereas the latter happens at compile-time and is part of the type system's process of ensuring type safety.

Recursive Types

Types can also be recursive, as in the type of binary trees:

data Tree a = Leaf a | Branch (Tree a) (Tree a)

Here we have defined a polymorphic binary tree type whose elements are either leaf nodes containing a value of type a, or internal nodes ("branches") containing (recursively) two sub-trees.

When reading data declarations such as this, remember again that Tree is a type constructor, whereas Branch and Leaf are data constructors. Aside from establishing a connection between these constructors, the above declaration is essentially defining the following types for Branch and Leaf:

Branch :: Tree a -> Tree a -> Tree a
Leaf :: a -> Tree a

With this example we have defined a type sufficiently rich to allow defining some interesting (recursive) functions that use it. For example, suppose we wish to define a function fringe that returns a list of all the elements in the leaves of a tree from left to right. It's usually helpful to write down the type of new functions first; in this case we see that the type should be Tree a -> [a]. That is, fringe is a polymorphic function that, for any type a, maps trees of a into lists of a. A suitable definition follows:

fringe :: Tree a -> [a]
fringe (Leaf x) = [x]
fringe (Branch left right) = fringe left ++ fringe right

Here ++ is the infix operator that concatenates two lists (its full definition will be given in Section 9.1). As with the length example given earlier, the fringe function is defined using pattern matching, except that here we see patterns involving user-defined constructors: Leaf and Branch. [Note that the formal parameters are easily identified as the ones beginning with lower-case letters.]

Type Synonyms

For convenience, Haskell provides a way to define type synonyms; i.e. names for commonly used types. Type synonyms are created using a type declaration. Here are several examples:

type String = [Char]
type Person = (Name,Address)
type Name = String
data Address = None | Addr String

Type synonyms do not define new types, but simply give new names for existing types. For example, the type Person -> Name is precisely equivalent to (String,Address) -> String. The new names are often shorter than the types they are synonymous with, but this is not the only purpose of type synonyms: they can also improve readability of programs by being more mnemonic; indeed, the above examples highlight this. We can even give new names to polymorphic types:

type AssocList a b = [(a,b)]

This is the type of "association lists" which associate values of type a with those of type b.