Type Declarations

Define a new name (synonym) for an existing type.

type String = [Char]

• Make other types easier to read

type Pos = (Int, Int)

origin :: Pos
origin = (0,0)

left
 :: Pos -> Pos
left (x, y) = (x-1, y)

• Can have parameters

type Pair a = (a, a)

mult :: Pair Int -> Int
mult (x, y) = x * y

• Can be nested

type Pos = (Int, Int)
type Trans = Pos -> Pos

• Can not be recursive

type Tree = (Int, [Tree]) -- Error

Data Declaration

Define a complete new type.

• Constructors: values for the type
• Type & constructors' names must begin with a upper-case letter
• Similar to context-free grammars

data Bool = False | True

• Values of new types can be used as the same way as those of built-in types

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

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

-- Circle & Rect can be views as functions that construct values of type Shape
Circle :: Float -> Shape
Rect :: Float -> Float -> Shape

• Data declarations can have parameters

data Maybe a = Nothing | Just a

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

p = case safediv 5 0 of
    Nothing -> 0
    Just x -> x + 1

Recursive Types

• New types can be declared in terms of themselves

data Nat = Zero | Succ Nat
Zero :: Nat
Succ :: Nat -> 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)
-- equals
add Zero n      = n 

add (Succ m) n  = Succ (add m n)

Arithmetic Expressions

data Expr = Val Int | Add Expr Expr | Mult Expr Expr
Val :: Int -> Expr

Add :: Expr -> Expr -> Expr
Mul :: Expr -> Expr -> Expr

-- 10 * (5 + 7)
e1 = Mult (Val 10) (Add (Val 5) (Val 7))

-- 10 + 5 * 7
e2 = Add (Val 10) (Mult (Val 5) (Val 7))

• Define functions that possess expressions

size :: Expr -> Int
size (Val n)       = 1
size (Add e1 e2)   = size e1 + size e2
size (Mult e1 e2)  = size e1 + size e2

eval :: Expr -> Int
eval (Val n)    = n
eval (Add m n)  = eval m + eval n
eval (Mult m n) = eval m * eval n

Binary Trees

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

t :: Tree Int
t  = Node (Node (Leaf 1) 3 (Leaf 4)) 5 (Node (Leaf 6) 7 (Leaf 9))

• Define functions that uses binary trees

occurs :: Ord a => a -> Tree a -> Bool
occurs x (Leaf y)     = x == y
occurs x (Node l y r) = x == y || occurs x l || occurs x r