COMP1100/1130 [2020 S1]:
PROGRAMMING AS PROBLEM SOLVING Research School of Computer Science
Menu
menu
» Labs » Week 3: Algebraic Data Types, Pattern matching, and Guards
In this lab we will look at algebraic data types, pattern matching with the case
command, and guarded expressions.
Table of Contents
Pre-Lab Checklist
Case Expressions
Guards
Testing your code with Doctest Area of a triangle done properly
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/2020s1studentZles/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 re[ect the change: https://gitlab.cecs.anu.edu.au/uXXXXXXX/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 enumeration types called Algebraic Data Types (ADT) with
Sum types
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.
Product types
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,
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
The expression
Exercise 1
Open Season.hs. You will Znd a pre-deZned function isCold.
We can execute ghci -Wall Season.hs and test how this function performs.
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?
Task 2
Since only one of the seasons return True, do we really need to pattern match against all four seasons?
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 they are useful.
Exercise 2
Create a new Zle and name it Mensuration.hs. On the Zrst 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 Zle.
Using the abstract data type (ADT) Shape deZned above, write a function area that calculates the area of a 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:
Submission required: Exercise 2 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.
d(s)
Your task is to use the Maybe type to stop this function throwing an error when the marks put in are out of bound. Write function markToGradeSafe with the type signature markToGradeSafe :: Mark -> Maybe Grade
Note that when the mark is within bounds, instead of a member X of the datatype 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 square root a negative number, and see whether the output is what you expect:
Prelude> 1 / 0 Prelude> sqrt (-1)
Submission required: Exercise 5 Exercise 6
Here’s another problem. At some point, you will want to Zgure out what GPA corresponds to which Grade. To simplify things, here’s a table modiZed from ANU GPA reference.
It would be handy if you could enter your mark, and it automatically calculated the GPA associated with that mark. e.g. if markToGPA 80 returned 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 GPA. Therefore the new function should have the type signature of Maybe Grade -> GPA where GPA is of the type Int.
You have already learnt that the Maybe type is deZned as follows: data Maybe a = Just a | Nothing. How do you actually utilise this in a productive way? Let’s start with an example:
The example above takes in a Maybe Int which is either Just Int or Nothing. If it follows the pattern of Just
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 next task is to write a function maybeGradeToGPA :: Maybe Grade -> GPA in
GPACalculator.hs. Note, if the Maybe Grade is Nothing, return 0. Submission required: Exercise 6
Exercise 7
Let’s link all of these stuff up together! Let’s list out the functions you’ve already written and are going to use:
markToGradeSafe :: Mark -> Maybe Grade – This takes a raw mark and outputs a 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 in Int (0 to 100) and outputs a GPA (0 to 7) associated with that mark.
Submission required: Exercise 7
Testing your code with Doctest
Exercise 8
Just because your code compiles, doesn’t mean it’s doing what it’s supposed to do. Consider the following:
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 Zgure out that it’s wrong before even compiling it. For a more complicated function, however, 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 wanted it to.
For example, if I compiled the above code and typed into GHCi: addOne 5, I would expect 6 to be the answer, but it would give me 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 Doctest, which we will extensively use throughout the semester.
What does a Doctest statement look like?
If we add the above code to a Zle called Adding.hs and run it with doctest Adding.hs, we obtain the following output:
which means that two test were present, one was ran (and it failed). Doctest will halt running tests as soon as any one of them fails. Here, doctest is reporting back that the output was 55, but the test says it should have been 6. This indicates the the behaviour of the code, and the tests do not agree. (Of course, it could be possible that the test itself is broken.)
Your job is to edit your Season.hs, GPACalculator.hs, and Mensuration.hs, so that they all utilise doctests to check the correctness of your functions.
Submission required: Exercise 8
Area of a triangle done properly
[COMP1100 Optional, COMP1130 Compulsory]
Exercise 9: 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 Zrst 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 Zle from previous lab to the current working directory. You can reuse some of that code in the next task.
The Zrst 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 deZnition, 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 Znal 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 have now all the tools at hand to do the job properly. Your new function areaOfTriangleSafe has the type:
areaOfTriangleSafe :: Double -> Double -> Double -> Maybe Double
and will return a numerical value as Just
Nothing for invalid triangles. Put all the bits from this lab together for this function. Write a few doctests for both valid and invalid triangles to justify your function.
References
[1] ANU Grade Point Average, http://www.anu.edu.au/students/program- administration/assessments-exams/grade-point-average-gpa
[2] Maybe type, http://hackage.haskell.org/package/base-4.12.0.0/docs/Data- Maybe.html
[3] Haskell Doctest, http://hackage.haskell.org/package/doctest
This lab contains additional exercises for COMP1130 students, which are optional but encouraged for COMP1100 students. Make sure that you submit attempts at all the exercises in order to receive full participation marks. The deadline for this is the start of your next lab.
data Season = Spring | Summer | Autumn | Winter deriving Show
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.
data Student = Person Name Age Gender deriving Show
johnSmith :: Student
johnSmith = Person “John Smith” 21 Male
case
Once you have opened the Zle, be sure to start ghcid using the instructions from lab02.
isCold :: Season -> Bool isCold season = case season of
Spring -> False Summer -> False Autumn -> False Winter -> False Winter -> True
*Season> isCold Summer
False
*Season> isCold Winter
False
[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.
Once you have created the new Zle, you will need to restart ghcid again using the instructions from lab02.
data Shape
= Circle Double — ^ Radius
| Square Double — ^ Side length
| Rectangle Double Double — ^ Width, Height
*Mensuration> area (Circle 10) 314.1592653589793 *Mensuration> area (Square 3) 9.0
*Mensuration> area (Rectangle 3 5) 15.0
Why area (Circle 10) and not area Circle 10? Try both, and see what happens.
— check whether an integer is even
isEven :: Int -> String isEven num
|modnum2==0 =shownum++”iseven.” –ifnumberiseven
| otherwise = show num ++ ” is not even.” — if the previous guar
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 |
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:
Task 1 Open GPACalculator.hs and then load the module in the terminal by executing ghci -Wall GPACalculator.hs in Bash. You will get the following warning:
Try out:
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.
Once the task is completed, reload the module, and try evaluating markToGrade 116 again. You should see the following:
Task 2
If you were to reload the module with -Wall [ag, you may get the following warning (if not, you can just read through this section, since you’ve already Zxed it):
What does this mean? Can you add a guard to Zx it? It should return an error message such as “markToGrade: Non-exhaustive guards in function”.
This is not a test. Ask your tutor or your classmate if you’re confused.
Submission required: Exercise 3 Exercise 4
A tuple is a Zxed number of values of Zxed types, that may be different, as a single object. For example, (String, Int) can be used to denote a course code and associated marks e.g. (“COMP1100”, 82), (“MATH1005”,92), etc.
Tuples are actually a primitive product type. Following from the example above
(“MATH1005”,92) :: (String, Integer) — A product of an String and Integer
You task is to write a function markToGrade’ that takes an input of the type (Course, Mark) and returns a Grade. Here Course is simply another name for the type String, Mark is another name for Int, and Grade is as deZned in Exercise 3.
Example outputs:
What happens when we enter an invalid mark as input?
Submission required: Exercise 4 Exercise 5
There are several other methods to handle exceptional values or situations which you will learn about. One method is to use types which can also hold some exceptional values on top of their “normal” value range. The simplest of those is the Maybe Type, which can hold values of a speciZc type or one special value (which is deZned as the value Nothing here). This way we can write function which will return (or accept) values which are of a speciZc type, but also have the option to say that they cannot return anything and actually returns the value Nothing instead.
For example, supposing you wrote a function to divide numbers. What should the function return if we divide by zero? It doesn’t seem sensible to return any number, and throwing an error and killing the program also may not be ideal (imagine if this software was running on an airplane, and a division by zero occurred, and the airplane’s computer shutdown mid-[ight. Not ideal.) Returning Nothing instead is a more graceful way to handle the case 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 of name choices, as it is not literally “nothing”, but in fact a special value. As it has established itself on planet Haskell though, we will also be using it here.
Consequently, the Maybe Type as already pre-deZned 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 grade program:
data Grade = Fail | Pass | Credit | Distinction | HighDistinction deriving Show
type Mark = Int
markToGrade :: Mark -> Grade markToGrade mark
| mark >= 80 &&
| mark >= 70 &&
| mark >= 60 &&
| mark >= 50 &&
| mark >= 0 && mark < 50 = Fail
mark <= 100 = HighDistinction mark < 80 = Distinction
mark < 70 = Credit
mark < 60 = Pass
GPACalculator.hs:14:1: warning: [-Wincomplete-patterns] Pattern match(es) are non-exhaustive
In an equation for ‘markToGrade’: Patterns not matched: _
*GPACalculator> markToGrade 116 …
*GPACalculator> markToGrade (-16) …
Hint: Have a look at the isEven function above for the guards syntax, and for returning an error, see the says function in the lecture about Case Expressions.
*GPACalculator> markToGrade 116
*** Exception: markToGrade: Not a valid mark CallStack (from HasCallStack):
error, called at GPACalculator.hs:20:32 in main:GPACalculator
GPACalculator.hs:14:1: warning: [-Wincomplete-patterns] Pattern match(es) are non-exhaustive
In an equation for ‘markToGrade’: Patterns not matched: _
Haskell is a language which takes code correctness and reliability very seriously. As such, it will give warnings for functions which it believes do not have a deZnition 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 which (when evaluating guard conditions from top to bottom) Haskell will always evaluate the function as the deZnition on the right hand side of the otherwise.
*GPACalculator> markToGrade’ (“COMP1100”, 45) Fail
*GPACalculator> markToGrade’ (“COMP2600”, 95) HighDistinction
See the following example for how you might write a safe division function using maybe types (maybe use something like this to write markToGradeSafe):
safeDiv :: Double -> Double -> Maybe Double safeDiv x y
| y == 0 = Nothing
| otherwise = Just (x / y)
Grade
Grade Point Value
HighDistinction
7
Distinction
6
Credit
5
Pass
4
Fail
0
maybeToInt :: Maybe Int -> Int maybeToInt m = case m of
Justi ->i Nothing -> 0
addOne :: Int -> Int addOne x = x + 50
— | Adding one. —
— >>>
— 6
—
— >>>
— 101
addOne 5
addOne 100
addOne :: Int -> Int addOne x = x + 50
Please remember to place the doctest above the function deZnition. 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.
> doctest Adding.hs
### Failure in Adding.hs:9: expression `addOne 5′
expected: 6 but got: 55
Examples: 2 Tried: 1 Errors: 0 Failures: 1
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.
The following are additional exercises for COMP1130 students, which are optional but encouraged for COMP1100 students. These exercises should only be attempted after completing all the exercises above. Feel free to do this at home and discuss with your peers on Piazza, or with tutors at a drop-in consultation.
Submission required for COMP1130 students: Exercise 9: Area of valid triangle.
Updated: 06 Jun 2020
Responsible Oqcer: Director, RSCS
Page Contact:
Course Convenor
Contact ANU
Copyright
Disclaimer
Privacy
Freedom of Information
+61 2 6125 5111
The Australian National University, Canberra CRICOS Provider : 00120C ABN : 52 234 063 906