In this lab we will look at algebraic data types, pattern matching with the case command, and guarded expressions.


Pre-lab Checklist

  • You should have completed Lab01 and Lab02.
  • You need to somewhat comfortable using Git with VSCodium.
  • You should have read through lectures up to Case Expressions in Week 2.

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/2024s2/2024s2studentfiles/comp1100-2024s2-lab03

  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/2024s2/2024s2studentfiles/comp1100-2024s2-lab03

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


Case Expressions

Quick Recap: In Haskell, you can create your own Algebraic Data Types (ADTs) using sum types, product types, and combinations of the two.

Sum types

data Season = Spring | Summer | Autumn | Winter
    deriving Show

The deriving Show gets GHC to automatically generate default code for converting a Season to a String. GHCi uses this when printing the value of an expression of type Season, which will make testing your code easier.

We will see later in the course precisely what the deriving keyword does in general, so don’t worry too much about it for now.

Product types

data Student = Person Name Age Gender
    deriving Show

Here, Person is called a data constructor (it holds everything together) and Name, Age, Gender are the types of the data inside this product type. So, for example,

johnSmith :: Student
johnSmith = Person "John Smith" 21 Male

You can also think of Person as a function of type

Person :: Name -> Age -> Gender -> Student

That is, it takes three inputs, the name, the age, and the gender, and uses this information to construct a Student.

Combining sum and product types

data Shape  = Circle Double | Rectangle Double Double

Case expressions can be used for pattern matching. Patterns can be literal values (2, 'a', True), variables, wildcard (_), tuples, other constructors etc. Case expressions allow you to match against the “shape” of the input, and extract out useful information from within.

Remember that case expressions have general syntax

case <expression> of
  <pattern1> -> <result1>
  <pattern2> -> <result2>
  ...

The expression <expression> is matched against each of the patterns <pattern1>, <pattern2>, … during evaluation in sequence from top to bottom. Once a pattern is matched, the function returns the corresponding result.


Exercise 1

Open Season.hs. You will find a pre-defined function isCold.

isCold :: Season -> Bool
isCold season = case season of
    Spring -> False
    Summer -> False
    Autumn -> False
    Winter -> False
    Winter -> True

We can type ghci -Wall Season.hs in Terminal to start the ghci interpreter (with all warnings turned on) and test how this function performs.

ghci> isCold Summer
False
ghci> isCold Winter
False

That doesn’t seem right, Winter is a cold season.

Task 1

Fix the function so that isCold Winter returns True. Hint: What do you think -Woverlapping-patterns in the following warning could mean?

[1 of 1] Compiling Season           ( Season.hs, interpreted )

Season.hs:12:5: warning: [-Woverlapping-patterns]
    Pattern match is redundant
    In a case alternative: Winter -> ...
   |
12 |     Winter -> True
   |     ^^^^^^^^^^^^^^
Ok, one module loaded.

Task 2

Since only one of the seasons returns True, do we really need to pattern match against all four seasons? Consider rewriting accordingly. Hint: You should only need two patterns.

Submission required: Exercise 1
Each exercise should be committed using Git integration in VSCodium as shown in Lab 02. Use an appropriate commit message, e.g. “Lab03: completed Ex1”. Feel free to write your own, as long as it is meaningful.


Exercise 2

Create a new file and name it Mensuration.hs.

On the first line, write:

module Mensuration where

VSCodium will probably automatically indent the next line, press backspace to return the cursor to the far left of the file.

Now, consider the algebraic data type Shape:

data Shape
  = Circle Double -- ^ Radius
  | Square Double -- ^ Side length
  | Rectangle Double Double -- ^ Width, Height

Write a function area that calculates the area of a given shape. You will need to use case expressions to check which kind of shape the input is, and then compute the area as appropriate. Feel free to look online if you are not sure of the mathematical formula required.

Thinking back to Lab 01:

  • What do you think should be the type signature of this function?
  • What do you think should be on the second line of this function?
  • What could you include as a comment for the function that is useful to the reader?

Example outputs:

ghci> area (Circle 10)
314.1592653589793
ghci> area (Square 3)
9.0
ghci> area (Rectangle 3 5)
15.0

Why area (Circle 10) and not area Circle 10? Try both, and see what happens.

Submission required: Exercise 2
Commit your work, as you did for Exercise 1.


Guards

There are several ways of writing conditional functions in Haskell – two important ones are case, as we have seen above, and guarded expressions, also known as guards. Let’s explore guards through an example:

-- check whether an integer is even
isEven :: Int -> String
isEven num
  | mod num 2 == 0 = show num ++ " is even."
    -- if number is even
  | otherwise      = show num ++ " is not even."
    -- if the previous guard(s) is not True

As the name suggests, a guarded expression is an expression which will only be reached if the associated guard (the Boolean expression right in front of it) evaluates to True. Each line | <guard> = <expression> of the function isEven can thus be read as: if <guard> then <expression> is returned. You may find the operators && (Boolean AND), the || operator (Boolean OR) and not (Boolean negation) useful for constructing Boolean expressions.


Exercise 3

Finding your grade at the ANU from your raw mark isn’t a smooth, continuous function, but it has discrete output values. Depending on your mark, your grade will be calculated as:

data Grade  = Fail | Pass | Credit | Distinction | HighDistinction
  deriving Show

type Mark = Int

markToGrade :: Mark -> Grade 
markToGrade mark
 | mark >= 80 && mark <= 100 = HighDistinction
 | mark >= 70 && mark < 80 = Distinction
 | mark >= 60 && mark < 70 = Credit
 | mark >= 50 && mark < 60 = Pass
 | mark >=  0 && mark < 50 = Fail

Task 1

Open GPACalculator.hs and then load the module into GHCi by executing the command ghci -Wall GPACalculator.hs in the Terminal. You will get the following warning:

GPACalculator.hs:14:1: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for ‘markToGrade’: Patterns not matched: _

Try out:

ghci> markToGrade 116
...
ghci> markToGrade (-16)
...

Since the mark is an Int, numbers below 0 and above 100 are also valid inputs, but not valid as a mark. Your task is to add a guard that returns an error message “markToGrade: Not a valid mark” if the input mark is strictly less than 0 OR strictly greater than 100.

Hint: Have a look at the isEven function above for the guards syntax, and for returning an error, see the lecture material on Case Expressions.

Once the task is completed, reload the module, and try evaluating markToGrade 116 again. You should see the following:

ghci> markToGrade 116
*** Exception: markToGrade: Not a valid mark
CallStack (from HasCallStack):
  error, called at GPACalculator.hs:20:32 in main:GPACalculator

Task 2

If you reload the module with the flag -Wall, you may get the following warning (if not, you can just read through this section, since you’ve already fixed it):

GPACalculator.hs:14:1: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for ‘markToGrade’: Patterns not matched: _

What does this mean? Can we modify our guarded expression to remove this warning?

Haskell is a language that takes code correctness and reliability very seriously. As such, it will give warnings for functions which it believes do not have a definition for every possible valid input (i.e., every possible value of the input(s) type). Even though it is likely that you have matched every possible Integer input to this function, Haskell isn’t sure, and so it gives the above warning. To satisfy Haskell, we typically will end a set of guards with an otherwise — upon reaching an otherwise case as the last line (when evaluating guard conditions from top to bottom) Haskell will always evaluate the function as the definition on the right hand side of the otherwise.

This is not a test. Ask your tutor or your classmate if you’re confused.

Submission required: Exercise 3.
Commit your work.


Exercise 4

A tuple is a pair of elements, possibly of different types. A 3-tuple is a triple of elements, a 4-tuple is a grouping of 4 elements, in general an N-tuple is a grouping of n elements for some n.

Tuples are useful when we want to group information together. In Haskell we represent tuple types with parentheses.

As an example, consider your overall grade for a particular course, we can represent this as a pair of a Course and a positive Integer like so: (Comp 1100, 85) or (Busn 1001, 97).

The tuple can be thought of as the Haskell representation of the product type.

(Math 1005,92) :: (Course, Integer) -- A product of a Course and Integer

Your task is to write a function markToGrade' that takes an input value of type (Course, Mark) and returns a Grade.

You can define Course as

data Course = Art Int -- Int denoted the course code
            | Comp Int 
            | Busn Int 
            | Math Int

As before, Mark is another name for Int, and Grade is as defined in Exercise 3.

Example outputs:

ghci> markToGrade' (Comp 1100, 45)
Fail
ghci> markToGrade' (Busn 1001, 95)
HighDistinction

Hint: This function can be written in a single line.

What happens when we enter an invalid mark as input?

Submission required: Exercise 4
Commit your work.


Exercise 5

There are several other ways to handle exceptional values or situations which you will learn about. One way is to use types that can also hold some exceptional values “on top of” their “normal” values. The simplest of these is the Maybe type, which can hold values of a specific type or one special value (which is defined as the value Nothing here). This way we can write function which will return (or accept) values that are of a specific type, but also have the option to say they cannot return anything and actually returns the value Nothing instead.

For example, supposing you write a function to divide numbers. What should the function return if we divide by zero? It doesn’t seem sensible to return any number at all (except perhaps the value infinity), and throwing an error and killing the program also may not be ideal (imagine if this software is running on an aeroplane, and division by zero occurs, so shutting down the plane’s control computer in mid-flight — not ideal!) Returning Nothing instead is a more graceful way to handle the situation where we would not otherwise be able to return a value.

After you have read the above you will probably notice that the name “Nothing” is perhaps not the most sensible choice of name, as it is not literally “nothing”, but in fact a special value. But, planet Haskell has defined it thus, so we are stuck with it here.

Consequently, the Maybe Type as already pre-defined in Haskell looks like this:

data Maybe a = Nothing | Just a

where a stands for “any type”. We can now write another version of our grading program.

Your task is to use the Maybe type to stop the markToGrade function throwing an error when the input mark is out of bounds. Write function markToGradeSafe with the type signature:

markToGradeSafe :: Mark -> Maybe Grade

Note that when the mark is within bounds, instead of a value X of the type Grade, we now return Just X, which is of type Maybe Grade. When the mark is out of bounds, we now return Nothing. Test your implementation of markToGradeSafe and see what GHCi displays as return values. Other numerical types use a similar concept. For instance, try to divide 1 by 0 in GHCi, or take the square root of a negative number, and see if the output is what you expect:

ghci> 1 / 0
...
ghci> sqrt (-1)

See the following example for how you might write a safe division function using a Maybe type (maybe use something like this to write markToGradeSafe):

safeDiv :: Double -> Double -> Maybe Double
safeDiv x y
    | y == 0 = Nothing
    | otherwise = Just (x / y)

Submission required: Exercise 5.
Commit your work.


Exercise 6

Here’s another problem. At some point, you will want to figure out what GPA corresponds to which Grade. To simplify things, here’s a table modified from ANU GPA reference.

Grade Grade Point Value
HighDistinction 7
Distinction 6
Credit 5
Pass 4
Fail 0

It would be handy if you could enter your mark, and it automatically calculated the GPA associated with that mark. For example, markToGPA 80 would return 7 as the result.

Let’s break this down to two steps. We have already written the part where you convert your mark to a grade. The next step is to write another function to convert grades to a GPA. Therefore the new function should have following type signature (where GPA is another name for Double): Maybe Grade -> GPA

You have already learnt that the Maybe type is defined as follows:

data Maybe a = Just a | Nothing

How do you actually use this productively? Let’s start with an example:

maybeToInt :: Maybe Int -> Int
maybeToInt m = case m of
    Just i  -> i
    Nothing -> 0

The example above takes in a Maybe Int which is either Just Int or Nothing. If it follows the pattern of Just <some Int value i>, return i, if it’s Nothing, return 0.

You can see we’ve used pattern matching here to “look inside” the input, and extract out the number contained inside the Maybe type (if such a number exists).

Have a closer look at the third line of this example — what is the type of i?

Your task is to add a new function to GPACalculator.hs:

maybeGradeToGPA :: Maybe Grade -> GPA

Note, if the Maybe Grade is Nothing, return 0.

Submission required: Exercise 6
Commit your work.


Exercise 7

Let’s link all of these things together! First, let’s recall the functions you’ve already written and are going to use:

  • markToGradeSafe :: Mark -> Maybe Grade: This takes a raw Mark and outputs a Maybe Grade.
  • maybeGradeToGPA :: Maybe Grade -> GPA: This takes a Maybe Grade and outputs a GPA associated with that grade.

What’s the next step?

Write a function: markToGPA :: Mark -> GPA, (using the functions already written to help you) which takes in a raw mark as an Int in the range 0 to 100 and outputs a GPA (0 to 7) associated with that mark.

Submission required: Exercise 7.
Commit your work.


Nesting guards and cases

A useful property of cases and guards is being able to nest them (i.e. use cases within cases).

Remember how we defined the data type Shape in section combining sum and product types.

Let us define a valid circle as a Circle with non-negative radius, and a valid rectangle as a Rectangle with non-negative length and width.

data Validity = Valid | Invalid

Using this let us define a function that takes a Shape and returns the Validity of that shape.

validShape :: Shape -> Validity
validShape shape = case shape of 
    Circle rad 
        | rad < 0 -> Invalid
        | otherwise -> Valid 
    Rectangle h w 
        | h < 0 || w < 0 -> Invalid 
        | otherwise -> Valid 

In this example we have used a guard within a case. The case checks what the shape is and the guard considers the criteria for the shape to be valid.

Note how the nested guard uses an -> and not a =

Exercise 8 (Tricky)

Using the above concept, we will be trying to remake the function markToGrade'. This time we are given the additional information that 1000 level Busn courses will be scaled down by 10% (i.e. multiplied by 0.90) and all other Busn courses will be scaled down by 5% (i.e. multiplied by 95%). All the other courses calculate the grade without scaling.

Submission required: Exercise 8. Commit your work.

Testing your code with Doctest


Exercise 9

Just because your code compiles, it doesn’t mean it will do what it is supposed to. Consider the following:

addOne :: Int -> Int
addOne x = x + 50

Does this compile? Of course it does! Does this do what it’s supposed to? Deducing from the name, it should take a number, and add one to it. However, what it actually does is to take a number and add 50 to it. For a simple functions like this, it’s relatively easy to figure out that it’s wrong before even compiling it. However, for a more complicated function it is often necessary to compile it and run the code with a pre-determined input and expected output, to see if it does what you want it to.

Loading the above function into GHCI, and typing: addOne 5, you might expect 6 to be the answer, but it actually gives the result 55. There is a useful tool in Haskell which takes away the manual labour of testing everything yourself. You simply tell it what to do, what to expect, and it will check the functions for you. This is called Doctest, which we will extensively use throughout the semester.

What does a Doctest statement look like?

-- | Adding one.
--
-- >>> addOne 5
-- 6
--
-- >>> addOne 100
-- 101

addOne :: Int -> Int
addOne x = x + 50

Please remember to place the doctests above the function definition. In this case, the doctests for the function addOne is written above the function. Note that doctests can be very picky about formatting, so you can use the above example to check against.

If you add the above code to a file called Adding.hs and run it with the command doctest Adding.hs, you should get the following output:

> doctest Adding.hs 
### Failure in Adding.hs:9: expression `addOne 5'
expected: 6
 but got: 55
Examples: 2  Tried: 1  Errors: 0  Failures: 1

This means that two tests were present, one ran (and failed). Doctest will stop running tests as soon as the first one fails. Here, doctest is reporting back that the output was 55, but the test says it should have been 6. This indicates that the behaviour of the code, and the tests do not agree. (Of course, it could be possible that the test itself is broken.)

Your task is to add doctests to at least one function in every module of this lab, namely Season.hs, GPACalculator.hs, and Mensuration.hs.

Submission required: Exercise 9. Commit your work.

You are required to submit your attempts at the exercises above in order to receive full participation marks for this lab. You have until the start of your next lab to do this. You should submit by committing and pushing all your changes to your Gitlab repository.


Area of a triangle done properly

[Optional, not required for participation marks]


Exercise 10: Is the triangle even valid?

If you look back at last week’s lab, you will now see that the function areaOfTriangle could not have been the last word. This function should not return an area value if the provided edge lengths cannot form a triangle. So as an intermediate step we will first write a function isValidTriangle that will tell you whether the sum of any two sides of the triangle is larger than the remaining side.

Copy the Area.hs file from Lab 2 to the current working directory. You can reuse some of that code in the next task and fix the definition of areaOfTriangle using isValidTriangle.

The first challenge is to work out what the type of the function should be (Hint: remember the output of the function can be either True or False). Write a type signature for the function.

Next write the actual function definition, which can well be a single line, or alternatively a sequence of guarded expressions. Test your function with some values in GHCi before you proceed to the final exercise. \(\{1, 2 ,4\}\) is for instance a set of edge lengths which cannot form a triangle. What does your function make of it?


Area of a valid triangle

You now have all the tools at hand to do the job properly. Your new function areaOfTriangleSafe has the type:

areaOfTriangleSafe :: Double -> Double -> Double -> Maybe Double

It will return a numerical value as Just <Double value> for all valid triangles and Nothing for invalid triangles. Put all the bits from this lab together for this function.

Write your function and a few doctests for both valid and invalid triangles to justify your function.

Submission: Exercise 10: Area of valid triangle.

References

[1] ANU Grade Point Average, http://www.anu.edu.au/students/program-administration/assessments-exams/grade-point-average-gpa
[2] Haskell Doctest, http://hackage.haskell.org/package/doctest

bars search times