This lab covers type classes and ad hoc polymorphism, and how we can use these concepts to generalise functions that require some assumptions about the input type. Stacks are also covered in this lab, showing you how you can use these data structures for different purposes.
 PreLab Checklist
 Getting Started
 Types
 Type Classes
 Applications of Type Classes
 Instances
 Deriving Type Classes
 Stacks
 Exercise 5
 Exercise 6
 Exercise 7
 Extensions (Optional)
PreLab Checklist
 You are comfortable with the concept of parametric polymorphism.
 You are comfortable with the recursive data type
Nat
from Lab 06
Getting Started

Go to the project’s dashboard under the Project tab and click on the Fork button. The gitlab url for this lab is https://gitlab.cecs.anu.edu.au/comp1100/2024s1/2024s1studentfiles/comp11002024s1lab10

You will be asked where to fork the repository. Click on the user or group to where you’d like to add the forked project. You should see your own name here. Once you have successfully forked a project, you will be redirected to a new webpage where you will notice your name before
> projectname
. This means you are now the owner of this repository. The url in your browser should reflect the change: https://gitlab.cecs.anu.edu.au/uXXXXXXX/comp11002024s1lab10 
Finally, clone your forked repository to your computer according to the instructions in the Week 2 Lab.

Put your exercise solutions in the file
Lab10.hs
. This file is prefilled with unfinished functions that match the exercises below.
This lab contains additional exercises for COMP1130 students. COMP1100 students are encouraged to attempt them once they have completed the compulsory exercises to receive the participation marks for the lab.
This is a long lab, and there are two main topics, both of which are of high importance. If you are still working on exercises 13 after the first hour, it is recommended that you skip to Exercise 4. Don’t stress though! This is just so you have a chance to ask your tutor questions about typeclasses, stacks and queues. As always, you can finish up any remaining questions afterwards before next week’s lab.
Types
We’ve seen before in Lab06 that some functions can be written to work on an arbitrary type, like length:
length :: [a] > Integer
length list = case list of
[] > 0
_:xs > 1 + length xs
The actual values of the elements in the list do not concern us, we only want to know how many there are, which is why this function can be written in a way that’s parametrically polymorphic, that is, it will work regardless of the type of the elements in the list.
Now we would like to generalise other functions. Consider the following function
sumInteger
:
sumInteger :: [Integer] > Integer
sumInteger list = case list of
[] > 0
x:xs > x + sumInteger xs
It’s possible to write the same function for types other than Integer
, like
Double
.
sumDouble :: [Double] > Double
sumDouble list = case list of
[] > 0
x:xs > x + sumDouble xs
Clearly this function cannot be made parametrically polymorphic, as the addition
operator +
isn’t defined for all types. (We can’t add together strings or
Boolean’s, for example.)
So we want a way to define the sum
function to operate over all lists that
contain types that “act like numbers”, that is, types where addition is well
defined. This is a weaker form of polymorphism, called adhoc polymorphism.
If we had just tried to make the type of sum
as general as possible by
changing the type signature to
sumEverything :: [a] > a
then we get the error message
No instance for (Num a) arising from a use of `+'
This is a rather cryptic way of saying “The input type can be anything, but
addition is only defined on things that are numbers, that is, types that belong
to the type class of Num
.” To solve this problem, we need to introduce type
classes.
Type Classes
Haskell handles adhoc polymorphism by using type classes, grouping types together into classes that all share similar properties, (they all act like numbers, they all have equality defined, etc.)
The main type classes you’re likely to see in Haskell are as follows:
Type Class  (some of the) functions defined  Description  Depends on? 

Show 
show 
Can be printed as a string  N/A 
Eq 
(==) , (/=) 
Has equality defined  N/A 
Ord 
<= , max , compare 
Has ordering defined  Eq 
Num 
(+) , (*) , () , abs , negate , signum , fromInteger 
Numbers, can perform arithmetic  N/A 
Fractional 
(/) , etc. 
Fractional numbers, can be divided  Num 
Floating 
sqrt , exp , log , sin ,cos , pi , etc. 
Acts like real numbers, many mathematical functions defined  Fractional 
Real 
toRational 
Numeric types that can be written as a rational  Num ,Ord 
Enum 
succ , pred , toEnum , fromEnum , etc. 
Sequentially ordered types  N/A 
Integral 
div , mod , etc. 
Acts like whole numbers, with integer division  Real , Enum 
Some types depend on others, and the type classes form a hierarchy.
If you
ever want to know more about a type, you can type in :info TypeName
into
GHCi
. It will also tell you what other types are instances, or belong to,
this type class.
ghci> :info Eq
class Eq a where
(==) :: a > a > Bool
(/=) :: a > a > Bool
instance Eq a => Eq [a]  Defined in ‘GHC.Classes’
instance Eq Word  Defined in ‘GHC.Classes’
instance Eq Ordering  Defined in ‘GHC.Classes’
instance Eq Int  Defined in ‘GHC.Classes’
instance Eq Float  Defined in ‘GHC.Classes’
instance Eq Double  Defined in ‘GHC.Classes’
instance Eq Char  Defined in ‘GHC.Classes’
instance Eq Bool  Defined in ‘GHC.Classes’
...
Here, we can see that members of the type class Eq
have the functions (==)
and (/=)
defined. We can also see that a few familiar types, Double, Char,
Bool, Int
all have equality defined on them. Digging deeper, we find the
interesting lines
instance Eq a => Eq [a]  Defined in ‘GHC.Classes’
instance (Eq a, Eq b) => Eq (a, b)  Defined in ‘GHC.Classes’
which tell us that if a type a
has equality defined, then so too does the type
[a]
. This is very powerful, as it saves on extra code that we don’t need
to write. As soon as you’ve told haskell how to compare integers, it can
automatically work out that [1,2] == [1,3]
should evaluate to False
.
The same goes for tuples: since Integer
and Char
both have equality defined,
so does (Integer, Char)
without any further work.
Applications of Type Classes
Consider the following function:
sum :: Num a => [a] > a
sum list = case list of
[] > 0
x:xs > x + sum xs
The notation
Num a => [a] > a
means that the function has type [a]
as input, and returns an element of type
a
as output, where a
is any type from the type class Num a
. So [Integer]
> Integer
, or [Double] > Double
are special cases of Num a => [a] > a
,
but [Double] > Integer
or [Bool] > Bool
is not.
If we want a type to be a member of two or more type classes, we can enforce this.
areTheyEqual :: (Eq a, Show a) => a > a > String
areTheyEqual x y
x == y = (show x) ++ " is equal to " ++ (show y)
otherwise = (show x) ++ " is not equal to " ++ (show y)
Here, we are enforcing that the input type has equality defined, and can be
turned into a string. Sometimes specifying two type classes is redundant, e.g.
(Ord a, Eq a) => ...
is the same as Ord a => ...
as Ord
is a subclass of
Eq
.
Exercise 1 (Optional)
This exercise is optional, and is here just to help you further get your head around type classes. If you feel confident, feel free to skip ahead to Exercise 2.
See if you can work out what type classes the following types belong to. You
might like to experiment and try out some operations in GHCi
(like trying to
compare two elements with <=
, or trying to add two elements together) to see
what is defined.
Integer
Double
Char
Bool
(Integer, Integer)
(Integer, Double)
String
[Integer]
Integer > Integer
Maybe Integer
Exercise 2
You can check your answers by asking
GHCi
what it had inferred the type to be, by entering :type functionName
.
 cow :: ???
cow x y z = x && (y `elem` z)
 foo :: ???
foo x y z = x `elem` y && y `elem` z
 bar :: ???
bar x y = case y of
Nothing > x
Just z > x + z
 snap :: ???
snap x y
x > y = show x
otherwise = show y
Submission required: Exercise 2 inferring types
Instances
When we create a new type, we would like to tell Haskell what type class our new type shall belong to. We use the following code,
instance TypeClass MyNewType where
...
which breaks down as:
instance
is a reserved keyword indicating we are adding a new type to a type classTypeClass
is the type class we want our new type to belong toMyNewType
is the name of our new type
We then have to define all the functions that a member of that type class should have defined.
 For the
Eq
type class, we need only(==)
, (and we get(/=)
for free.)  For
Ord
, we need to already be inEq
, and then also define either(<=)
orcompare
(and Haskell can work out all the other operators like(<)
,(>)
,(>=)
for free.)
If you’re interested, you can look at the documentation for the Prelude, and under each type class, the minimal complete definition tells you the fewest functions that you need to define, and then the rest are automatically derived for you.
For example, (see Fruit.hs
) suppose we define a new type for fruit,
data Fruit = Apple  Banana  Orange
and we wanted to define equality on our fruit. We need to tell Haskell what
(==)
means for fruit.
instance Eq Fruit where
Apple == Apple = True
Banana == Banana = True
Orange == Orange = True
_ == _ = False
So we define equality in the obvious way. All fruits are equal to themselves, and any fruit is not equal to a different fruit.
Note that there was nothing forcing me to define equality in this way,
I could have defined Apple == Banana
to be True
but
Banana == Apple
to be False
. This doesn’t mean that we should, though.
To do so would be very poor style, and go against the
Haskell standard.
I can also define what it means to show a Fruit
.
instance Show Fruit where
show fruit = case fruit of
Apple > "An apple."
Banana > "A banana! Yum!"
Orange > "Yuck, an orange."
So when I type Banana
into GHCi
, a Banana
is printed to the terminal using
my custom definition for show
.
> Banana
A banana! Yum!
I can also define ordering on fruit. I’m going to order fruit by how much I
enjoy eating them: Banana
being the best, Apple
being okay, and Orange
is
the worst. (Deepest apologies to those that love oranges.)
If we give a full definition of the (<=)
function:
instance Ord Fruit where
(<=) Orange Apple = True
(<=) Apple Banana = True
(<=) Orange Banana = True
(<=) Banana Apple = False
(<=) Apple Orange = False
(<=) Banana Orange = False
(<=) Banana Banana = True
(<=) Apple Apple = True
(<=) Orange Orange = True
then Haskell can use that to define all the usual ordering operators:
> (Banana > Orange)
True
You’ll note how tedious it is to write out all the cases. Surely if
Orange <= Apple
and Apple <= Banana
, then Orange <= Banana
, right?
Sadly, Haskell doesn’t place any sensible constraints on the <=
function we
define. It’s up to the user to define <=
in such a way that the usual
ordering
properties
you would expect, are satisfied.
Deriving Type Classes
Rather than doing the hard work ourselves, we can ask Haskell to define a lot of
these properties for us, using the deriving
keyword.
data Fruit = Orange  Apple  Banana
deriving (Ord, Show)
Haskell will assume the equality you wanted is the “obvious” implementation, that every fruit is equal to itself, and that no two different fruits are equal.
It will also place a ordering on fruit, on the order they appear in the
definition of Fruit
, so Orange
is less than Apple
, which is in turn less
than Banana
. The default definitions of equality and ordering Haskell provides
satisfy all the nice properties you would expect them to. The default
implementation of show
will also print each fruit exactly as they are defined.
> show Banana
"Banana"
Type classes where you can ask Haskell to do the hard work (defining all the
functions automatically) for you are called derivable classes. Not all type
classes are derivable. If we tried to add arithmetic to our fruit by making it a
member of the type class Num
,
data Fruit = Orange  Apple  Banana
deriving (Ord, Show, Num)
then Haskell will throw an error
Fruit.hs:4:14:
Can't make a derived instance of `Num Fruit':
`Num' is not a derivable class
and inform you that it doesn’t know how to define arithmetic on Fruit
. What
should Apple + Banana
be? What about Banana * Orange
? There’s no obvious way
to define it.
Exercise 3
Recall our definition of Nat
from
Lab 06.
data Nat = Z  S Nat
deriving Show
We’d like to define equality on natural numbers: Two arbitrary natural numbers
are equal if they have the successor S
applied the same number of times.
(==)
for
the type Nat
.
Do not use deriving Eq
here. You should define equality yourself.
Submission required: Exercise 3`
Exercise 4
It’s possible to place an ordering on natural numbers as follows:
Z < (S Z) < S (S Z) < ...
So if we want to ensure Nat
belongs to the type class Ord
, we need only to
define a definition of (<=)
, and Haskell can work out corresponding
definitions for all the other operators defined on Ord
: (<)
, (>)
, max
,
min
, compare
.
(<=)
for
the type Nat
.
Do not use deriving Ord
here. You should define equality yourself.
> Z >= (S Z)
False
> max (S Z) (S (S Z))
(S (S Z))
> (S Z) == (S Z)
True
> (S Z) == (S (S Z))
False
Submission required: Exercise 4`
Stacks
Stacks are Last In First Out data structures, which means that the last item pushed on to the stack should be the first one returned using the pop function. A stack can be implemented using a list, as was shown in the lectures.
data ListStack a = ListStack [a]
Stacks are useful for many applications. One such application is for exploring a maze. Suppose that you are trying to solve a maze. Whenever you reach a branching point in the maze, where there are several possible directions, e.g. turn left, turn right or stay straight, all the choices are pushed on to the stack. Then, one of the choices is popped and you try exploring that direction. If you reach another branching point, you push all the possible directions on to the stack again, and so on. When you reach a dead end, you need to backtrack. To do that, you just pop the last item from the stack, and try following that direction instead.
For example, suppose that you reach Branch 1 and push Straight, Left and Right on to the stack. Then, you pop Right and try exploring to the right. You reach Branch 2 and push Straight, Left and Right on to the stack. You pop Right and try exploring that direction. However, you reach a dead end. Then you pop from the stack, giving you Left. This means that back at Branch 2, you now try turning left. You keep going like that until you’ve tried all of the Branch 2 choices. Then, when you pop again, you’re now selecting a different path from Branch 1.
 Branch 1: Push Straight, Push Left, Push Right
 Pop  returns Right (selecting the Right direction from Branch 1).
 Branch 2: Push Straight, Push Left, Push Right
 Pop  returns Right (selecting the Right direction from Branch 2).
 Dead end.
 Pop  returns Left (selecting the Left direction from Branch 2).
 Dead end.
 Pop  returns Straight (selecting the Straight direction from Branch 2).
 Dead end.
 Pop  returns Left (selecting the Left direction from Branch 1).
 and so on until one of the paths leads to the exit of the maze.
For the following tasks, use the following data type:
data Direction = MazeLeft  MazeRight  MazeStraight deriving Show
Exercise 5
mazeChoice
that takes a stack and returns
the stack with the three directions pushed on to the stack (MazeLeft, MazeRight and MazeStraight).
mazeChoice :: ListStack Direction > ListStack Direction
Submission required: Exercise 5
Exercise 6
getLastChoice
that takes a stack and returns
a pair of a Maybe Direction (which is the last direction that was pushed on to the stack) and the
stack with that direction removed. If the stack does not have any directions in it, this function
should return a pair containing Nothing and an empty stack.
getLastChoice :: ListStack Direction > (Maybe Direction, ListStack Direction)
Submission required: Exercise 6
Exercise 7
printStackDir
that takes a stack of type ListStack Direction
and prints the contents of the stack from top to bottom. You can use this function to check
whether your other maze functions are working correctly.
printStackDir :: ListStack Direction > String
Submission required: Exercise 7
Extensions
[COMP1100 Optional, COMP1130 Compulsory]
Extension 1
Write a function revWithStack
which reverses a given list using a stack. Your
function must use a stack to do the reversal.
revWithStack :: [a] > [a]
Hint: You will probably need some helper functions which would have ListStack as a parameter.
Submission required for COMP1130 students: Extension 1 revWithStack
Extension 2
Nat
acts like a number, so we’d also like it to be a member of the type class
Num
.
For those that are mathematically inclined, the operators (+)
and (*)
can
actually be far more general than just addition and multiplication. The general
term for any structure containing a set of values, a definition for \(+\) and
for \(\times\) is called an algebraic ring, which you may see if you go on
to study formal mathematics. In general, (+)
and (*)
can be any operator
that satisfies a set of “nice proprieties”, such as the law of
distributivity: x * (y + z) == (x * y) + (x * z)
. The full set of laws that
(+)
and (*)
should satisfy is available
here.
As an example, if we choose (+)
to be logical exclusive or, and (*)
to be
logical and, then we can define Bool
as an instance of Num
, and all the nice
properties hold.
(+),(),(*),abs,signum,fromInteger
for the Nat
type.
Note that for an instance a
of Num
:
abs :: a > a
is the absolute value functionsignum :: a > a
returns the sign of a number, \(+1\) if the number is positive, \(0\) if the number is zero, and \(1\) if it is negative.fromInteger :: Integer > a
takes anInteger
, and converts it to the new number typea
.
You can get away without a definition for negate
, as once ()
is defined, Haskell can work out negate
for free.
(Given that natural numbers cannot be negative anyway, the negate
function
is not very useful to us.)
Note that some of the functions required to make Nat
an instance of Num
may be sometimes undefined. There is no “minus one”
in Nat
, after all. Try to ensure as many functions are defined
as possible, for as many inputs as possible.
You should throw an error for attempting to perform any operation
undefined in the natural numbers, like trying to compute 2  3
.
> (S Z) + (S (S Z))
(S (S (S Z)))
> (S Z)  (S Z)
Z
> (S (S Z)) * (S (S (S Z)))
S (S (S (S (S (S Z)))))
> (fromInteger 2) :: Nat
S (S Z)
> (S Z)  (S (S Z))
*** Exception: Can't have negative natural numbers
Submission required for COMP1130 students Extension 2 Nat
as an instance
of Num
Extension 3
We’d like to be able to define equality on binary trees based on the elements in
the tree. If we just used deriving Eq
, then two trees would be identical if
they have precisely the same elements and structure.
For the purposes of this question, we will define equality on binary trees to be the following weaker definition: Two trees are defined to be equal if they share the same elements, with the same ordering (although the structure need not be the same).
Since we want this definition to work on any tree with elements who have equality defined on them, we use the following notation.
instance (Eq a) => Eq (BinaryTree a) where
 (==) ...
which means that we are defining what ==
means for anything
of type BinaryTree a
, where a
must be a member of the type class Eq
.
Try come up with some other test cases to verify this function works. You may wish to draw them out by hand first.
Submission required for COMP1130 students: Extension 3