Learning goals

• To understand how type, newtype and data declarations work and how they differ.
• To be able to define functions over recursively defined data types using pattern matching.
• To understand how recursively defined data types can be used to implement the formation rules of a language.
• To understand the notion of term constructors and how they are used.
• To understand the principles of and be able to declare new instances of type classes.
• To understand how the above notions can be applied in the setting of a larger program.

Note that data declarations are also known as algebraic datatypes elsewhere.

Type declarations

You can define a new name for an existing type with a type declaration:

type String = [Char]
type Pos = (Int, Int)

-- You can give parameters
type Pair a = (a, a)

Type declarations can be nested, but not recursive!

Newtype

If your defined type has a single constructor with a single argument, you could use newtype.
E.g. a type of natural numbers could be:

newtype Nat = N Int

-- Similar to
type Nat = Int
data Nat = N Int

Using newtype ensures that, in the above example, Nat and Int aren’t synonyms, but different types. So the type checker will prevent mix-ups.

Data Declarations

You can define a competely new type by specifying its values using a data declaration:

data Bool = False | True

The two values (T/F) seen above are called constructors for the type Bool. Type and constructor names must always begin with an upper-case letter. Data declarations are similar to CFGs. The former specifies the values of a type, while the latter the sentences of a language.

Example

data Answer = Yes | No | Unknown

answers :: [Answer]
answers = [Yes, No, Unknown]

flip :: Answer -> Answer
flip Yes = No
flip No = Yes
flip Unknown = Unknown

Constructors can have parameters

-- Circle and Float can be seen as constructors.
data Shape = Circle Float | Rect Float Float

square :: Float -> Shape
square n = Rect n n

area :: Shape -> Float
area (Circle r) = pi * r^2
area (Rect x y) = x * y

Data declarations can have parameters

Maybe already exists, this just shows its declaration:

data Maybe a = Nothing | Just a -- Maybe represents something that can fail.

safediv :: Int -> Int -> Maybe Int
safediv _ 0 = Nothing
safediv m n = Just (m `div` n)

safehead :: [a] -> Maybe a
safehead [] = Nothing
safehead xs = Just (head xs)

Recursive Types

data Nat = Zero | Succ nat

nat2int :: Nat -> Int
nat2int Zero = 0
nat2int (Succ n) = 1 + nat2int n

int2nat :: Int -> Nat
int2nat 0 = Zero
int2nat n = Succ (int2nat (n-1))

add :: Nat -> Nat -> Nat
add m n = int2nat (nat2int m + nat2int n)
-- or, using recursion
add Zero n = n
add (Succ m) n = Succ (add m n)

Arithmetic Expressions example

data Expr = Val Int
	| Add Expr Expr
	| Mul Expr Expr
	
-- example: add (Val 1) (Mul (Val 2) (Val 3))
-- which is: 1 + 2 * 3

size :: Expr -> Int
size (Val n) = 1
size (Add x y) = size x + size y
size (Mul x y) = size x + size y

eval :: Expr -> Int
eval (Val n) = n
eval (Add x y) = eval x + eval y
eval (Mul x y) = eval x * eval y

Class and instances declarations

class Eq a where
	(==), (/=), :: a -> a -> Bool

	x /= y = not (x == y)

Says: For a type a to be an instance of the class Eq, it must support equality and inequality operators of the specified types.
It also includes a default definition for the /= operator, so declaring an instance only requires a definition for the == operator
So you might make the Bool type into an equality type like so:

instance Eq Bool where
	False == False = True
	True == True = true
	_ == _ = False

You can extend classes to make new ones, e.g. like so:

class Eq a => Ord a where
	(<), (<=), (>), (>=) :: a -> a -> Bool
	min, max :: a -> a -> a

	min x y | x <= y    = x
			| otherwise = y

	max x y | x <= y    = y
			| otherwise = x

Which is actually how the Ord class is defined in the prelude.
It means that, for a type to be an instance of Ord, it must be an instance of Eq, but also support the denoted operators.

Derived instances

When you declare a new type, you’d usually also make them instances of some built-in classes.

You use the deriving mechanism for this.

Here’s how the type Bool is declared in the prelude:

data Bool = False | True
	deriving (Eq, Ord, Show, Read)

And the result of this is that all member functions of the derived classes can be used with logical values. E.g. False == False.

Flashcards