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.

Pre-Lab Checklist

  • You are comfortable with the concept of parametric polymorphism.
  • You are comfortable with the recursive data type Nat from Lab 06

Getting Started

  1. 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/comp1100-2024s1-lab10

  2. 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 > project-name. 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/comp1100-2024s1-lab10

  3. Finally, clone your forked repository to your computer according to the instructions in the Week 2 Lab.

  4. Put your exercise solutions in the file Lab10.hs. This file is pre-filled 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 1-3 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 type-classes, 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 ad-hoc 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 ad-hoc 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

Try and work out the type of the following functions. Try to make the type as general as possible.

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 class
  • TypeClass is the type class we want our new type to belong to
  • MyNewType 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 in Eq, and then also define either (<=) or compare (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.

Using the template given, define the function (==) 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.

Using the template given, define the function (<=) 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

Write a function 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

Write a function 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

Write a function 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.

Using the template given, define the functions (+),(-),(*),abs,signum,fromInteger for the Nat type.

Note that for an instance a of Num:

  • abs :: a -> a is the absolute value function
  • signum :: 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 an Integer, and converts it to the new number type a.

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).

Add an instance of equality for binary trees that satisfies this weaker definition of equality.

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

bars search times arrow-up