8. Declaring types and classes

8.1 Type declarations

new name for an existing type

type String = [Char]

name of type MUST begin with upper-case letter

In [37]:
type Pos = (Int,Int)
type Trans = Pos -> Pos

Type declarations cannot be recursive; so the following is not allowed:

type Tree = (Int,[Tree])

Type declarations can be parameterized by other types:

In [38]:
type Pair a = (a,a)
(10,10) :: Pair Int
("John","Alice") :: Pair [Char]

(10,10)
("John","Alice")
In [39]:
type Assoc k v = [(k,v)]
[("John",32),("Alice",22)] :: Assoc [Char] Int
t = [("John",[10,20,30]),("Alice",[1,2,3])] :: Assoc [Char] [Int]

[("John",32),("Alice",22)]
In [40]:
find :: Eq k => k -> Assoc k v -> v
find k t = head [v | (k',v) <- t, k' == k]

find "Alice" t
find "John" t
find "James" t

[1,2,3]
[10,20,30]
Prelude.head: empty list

8.2 Data declarations

A completely new type can be defined using the data mechanism of Haskell

data Bool = False | True

Here, | is read as "or" and the values are "constructors"; constructors MUST begin with upper-case letters

In [41]:
-- another example
data Move = North | South | East | West deriving Show

move :: Move -> Pos -> Pos
move North (x,y) = (x,y+1)
move South (x,y) = (x,y-1)
move East  (x,y) = (x+1,y)
move North (x,y) = (x-1,y)

moves :: [Move] -> Pos -> Pos
moves []     p = p
moves (m:ms) p = moves ms (move m p)

rev :: Move -> Move
rev North = South
rev South = North
rev East  = West
rev West  = East
Use foldl
Found:
moves [] p = p moves (m : ms) p = moves ms (move m p)
Why Not:
moves ms p = foldl (flip move) p ms

another example

Constructors in data declarations may have arguments

In [42]:
data Shape = Circle Float | Rect Float Float deriving (Eq,Ord,Show)
In [43]:
square :: Float -> Shape
square n = Rect n n
In [44]:
area :: Shape -> Float
area (Circle r) = pi * r^2
area (Rect x y) = x * y
In [45]:
area (Circle 3)

28.274334
In [46]:
area (Rect 2 4)

8.0
In [47]:
:type Circle
Circle :: Float -> Shape
In [48]:
:type Rect
Rect :: Float -> Float -> Shape

So, in fact the constructors are actually constructor "functions", but are different from ordinary functions in that these are fully evaluated and are just pieces of data

In [49]:
Circle 3
Rect 1.0 4.0

Circle 3.0
Rect 1.0 4.0
In [50]:
negate 1.0

-1.0

parameterized data declarations

In [51]:
data Maybe a = Nothing | Just a deriving Show

Nothing represents "failure" and Just a represents "success"

In [52]:
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)
In [53]:
safediv 12 0
safediv 12 5
safehead []
safehead [1,2,3]

Nothing
Just 2
Nothing
Just 1

8.3 Newtype declaration

If a new type has a single constructor with a single argument, we can define it as follows:

newtype Nat = N Int

The programmer will have to ensure that no negative numbers are assigned as values to variable sof Nat type

So, the question arises on the differences between the following three:

newtype Nat = N Int
type Nat = Int
data Nat = N Int

As the name suggests, newtype creates a new type! whereas type creates an alias for another type. So, in

newtype Nat = N Int

Nat and Int are two different types. So, values cannot be interchangeably used. But in

type Nat = Int

Nat is another name for Int.

The main difference between newtype and data declaration is efficiency in implementation. In a newtype after compile-time checks are made, the compiler would substitute the types at run-time. So, no new constructors need be called at run-time. Whereas in a data declaration, this is not so.

8.4 Recursive types

New types declared vis data or newtype mechanisms can be recursive.

In [54]:
data Nat = Zero | Succ Nat deriving Show
In [55]:
Zero
Succ Zero
Succ (Succ Zero)
Succ (Succ (Succ Zero))

Zero
Succ Zero
Succ (Succ Zero)
Succ (Succ (Succ Zero))
In [56]:
nat2int :: Nat -> Int
nat2int Zero = 0
nat2int (Succ n) = 1 + nat2int n

int2nat :: Int -> Nat
int2nat 0 = Zero
int2nat n = Succ (int2nat (n-1))
In [57]:
nat2int (Succ (Succ (Succ Zero)))

3
In [58]:
int2nat 4

Succ (Succ (Succ (Succ Zero)))
In [59]:
add :: Nat -> Nat -> Nat
add m n = int2nat (nat2int m + nat2int n)
In [60]:
nat2int (add (Succ (Succ Zero)) (Succ (Succ (Succ Zero))))

5
In [61]:
add2 :: Nat -> Nat -> Nat
add2 Zero     n = n
add2 (Succ m) n = Succ (add2 m n)
In [62]:
nat2int (add2 (Succ (Succ Zero)) (Succ (Succ (Succ Zero))))

5
  add2 (Succ (Succ Zero)) (Succ Zero)
= Succ (add2 (Succ Zero) (Succ Zero))
= Succ (Succ (add2 Zero (Succ Zero)))
= Succ (Succ (Succ Zero))

list structure

In [63]:
data List a = Nil | Cons a (List a)
In [64]:
len :: List a -> Int
len Nil    = 0
len (Cons _ xs) = 1 + len xs
In [65]:
len (Cons 10 (Cons 20 (Cons 30 Nil)))

3

binary tree structure

In [66]:
data Tree a = Leaf a | Node (Tree a) a (Tree a) deriving Show
In [67]:
t :: Tree Int
t = Node (Node (Leaf 1) 3 (Leaf 4)) 5 
         (Node (Leaf 6) 7 (Leaf 9))
In [68]:
-- not assuming a binary search tree
occurs :: Eq 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
In [69]:
occurs 6 t
occurs 2 t

True
False
In [70]:
flatten :: Tree a -> [a]
flatten (Leaf x)     = [x]
flatten (Node l x r) = flatten l ++ [x] ++ flatten r
In [71]:
flatten t

[1,3,4,5,6,7,9]

-- assuming a binary search tree occurs :: Ord a => a -> Tree a -> Bool occurs x (Leaf y) = x == y occurs x (Node l y r) | x == y = True | x < y = occurs x l | otherwise = occurs x r

In [72]:
occurs 6 t
occurs 2 t

True
False

concluding remark regarding Tree

Trees can come in various forms:

  • binary trees with data only in leaves
  • binary trees with data only in interior nodes
  • binary trees with data of different types in leaves vs interior nodes
  • general trees (more than 2 child nodes)
data Tree a = Leaf a | Node (Tree a) (Tree a)
data Tree a = Leaf   | Node (Tree a) a (Tree a)
data Tree a b = Leaf a | Node (Tree a b) b (Tree a b)
data Tree a = Node a [Tree a]