程序代写代做 game Haskell go algorithm compiler database data structure interpreter html COMP1100/1130 [2020 S1]:

COMP1100/1130 [2020 S1]:
PROGRAMMING AS PROBLEM SOLVING Research School of Computer Science
Menu
menu
» Labs » Week 7: Style and Testing
This lab covers two aspects of code quality: style, which is the way to write readable
code; and verifying correctness via testing.
Table of Contents
Pre-Lab Checklist Learning Outcomes Haskell Style Testing in Haskell Extensions
Pre-lab Checklist
You should have watched the lectures from week 06.
You should be able to write doctests, as introduced in Lab03 You should have completed all lab tasks till at least Lab05.
Learning Outcomes
Develop techniques to write Haskell code with consistent style
Develop understanding behind black box and white box testing and be able to write tests appropriately
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/2020s1student`les/lab07
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 reaect the change: https://gitlab.cecs.anu.edu.au/uXXXXXXX/lab07
3. Finally, clone your forked repository to your computer according to the instructions in the Week 2 Lab.
Haskell Style
This section will lead you through developing a program with good Haskell style. Assignments 2 and 3 will contain marks explicitly assigned to coding style, so it is worth your time to learn to write readable code according to these guidelines. This section has been heavily inauenced by some online Haskell style guides; please see references at the end of the lab.
Module
A module is the name given by Haskell to a .hs `le containing a collection of related types and functions.
Naming
Module names should
start with a capital letter
use CamelCase
be singular e.g. Tree instead of Trees
Documentation
The `rst item in your module should be the module level documentation, using the following format:
Exercise 1
You can create a new `le in VSCodium by following these instructions: 1. Right click in the left “Explorer” bar
2. Select “New File”
3. Give the `le an appropriate name
Submission required: Exercise 1
Exercise 2
Submission required: Exercise 2
Type Declarations Naming
Type names should
start with a capital letter use CamelCase
Documentation
Constructors are documented like this, with comments for each constructor:
Exercise 3
Copy the code below to give type aliases for Name, Year and Availability:
Once you have de`ned Video, we can de`ne a Library as: type Library = [(Video, Availability)]
Submission required: Exercise 3
List Declarations
If a list is too long to be written down without exceeding 80 characters of width, you will have to use several lines. Align these lines with consistent indentation. As an example, we can list the availability of a number of videos:
You may `nd it useful to copy this list of videos in the current module.
Functions Naming
Function names should
start with lower case
use camelCase e.g. sumList, sumUpTo
be descriptive to reaect the intended use of the function
Type Declaration
Every top-level function must have an explicit type declaration. For example, write
instead of just
Not only does it make your code easier to read, it also means that Haskell will return nicer error messages if you try to input the wrong thing, as it will know what type you intended the function to have.
Documentation
Most top-level declarations (data types and functions) should be preceded by a short comment, written with Haddock syntax.
Comments should say what the code does, not how it does it. It should be obvious how the code works, just by looking at it. If this is not the case, you need to rewrite the code.
Do not over-comment.
Very many or very long comments (especially within the body of a function) are more distracting than helpful. Long comments may appear at the top of a `le or section of code, if you need to explain the overall design of the code or refer to sources that have more information about the algorithms or data structures. All other comments in the `le should be as short as possible. Judicious choice of variable names can help minimize the need for comments.
Avoid comments that state the obvious:
Use proper English.
Comments need not always be written in complete sentences, but when they are, standard rules of English grammar apply. Spelling also counts.
Exercise 4
What would be the type signature of this function? Once you `gure it out, check with your classmates and/or your tutor to see what they think.
Hint: You may `nd it useful to de`ne a helper function getName that takes a Video as input and returns the name.
Submission required: Exercise 4
Formatting Line Length
Maximum line length is 80 characters. If your code is longer than 80 characters, you should
think about helper functions to do part of task otherwise, wrap your code syntantically
Indentation
Do not use tabs. Use spaces for indenting.
Indent your code blocks with at least 2 spaces, and be consistent throughout your code.
Exercise 5
What should be the type signature of this function? Feel free to discuss this with your classmates and/or tutor.
Submission required: Exercise 5
Warnings
Code you write should always be compiled with -Wall. There should be no warnings, if there are, make sure to `x your code to get rid of them.
Testing in Haskell
The aim of this section is to guide you through the formulation of unit tests which will help you to establish the correctness of functions that you write.
The type signature of the function will be:
secondMinimum :: [Int] -> Maybe Int DO NOT START WRITING CODE YET!!!
As discussed in Code Quality lecture, we will use two testing techniques:
Black box testing: testing without looking at the code, and usually designed before the code is written;
White box testing: testing inspired by the code that is written.
Exercise 6: Black Box Testing
Our input is a list of integers, so we will want to choose lists of integers that help us to test various behaviours of our future program.
on an empty list we should return Nothing
are there any other cases that should return Nothing? Could you separate them into different testing groups? What examples from each group would you choose to test?
this code is supposed to return the second smallest value; so on the list [1,2,1] it should return 2. Is this a good example to test? Why or why not?
are there any other testing groups suggested by this problem, before you write a line of code? What examples from these groups could you test?
Submission required: Exercise 6
Exercise 7
Write the function secondMinimum. Check that it passes all your black box tests.
Submission required: Exercise 7
Exercise 8: White Box Testing
As you write the function, you may notice that you require more tests to be sure that your function is correct. For example, you may decide to use one or more helper functions; you can write tests speci`cally for these functions. These white box tests are motivated by your code, and because there are many different ways to write secondMinimum, your white box tests may be quite different from those of others in your lab.
In particular, once you have `nished your code, you should see if you require any further tests motivated by the following code features:
If your function contains case statements or guards, you should include tests for each case or guard. If there are boundaries between your cases or guards where they meet or overlap, write tests especially for those boundaries;
If you use recursion, you should test the base case, the single element case and the general step case.
Submission required: Exercise 8
Note: We chose to use doctest as the testing framework in this lab, since this is familiar to you from previous labs. You will notice that using a large number of doctests can make your source `le look quite “bulky”. It is better style in such a case to use a testing framework involving a separate `le, as in the assignments, but you are not required to do so for this lab.
Exercise 9
Submission required: Exercise 9
Evaluating Numerical Expressions [COMP1100 Optional, COMP1130 Compulsory]
Given the task to evaluate an expression like “3 + 4 * 5 ^ 6” when typed into GHCi as a String, how would you go about it? Of course one has to think about operator precedence, but leaving that aside, `rst think how you would evaluate an expression like “3 + 4 – 5 + 6” and maybe expressions with aoating point numbers like “3.2 – 4.2 – 5.3 + 6.3”.
Before we go too far ahead, we need to think about how to represent the expression effectively. Having an expression like that represented as a String while you are working on it will turn into a programming massacre very quickly. Hence, every evaluation system—compiler, interpreter, or even your GHCi—will always perform what is called lexical scanning or tokenisation, converting the program text you type into a more structured (typed) form `rst. For instance we could store expressions like the one above as a “list of tokens”:
So “3.2 – 4.2 – 5.3 + 6.3” translates into:
[Num 3.2, Minus, Num 4.2, Minus, Num 5.3, Plus, Num 6.3]
This translation is done by going through the original string once, from left to right, and converting it into a list of tokens. This function is often called a scanner (since it scans from beginning to end), or a lexer (because it recognizes the lexical units or lexemes of some language) or a tokeniser (as lexemes are often called tokens). It is an essential step for lexical analysis as the `rst phase of translating programs written in a given programming language. If you have the pleasure of implementing a programming language in a few years (perhaps even one you design yourself), then you will certainly learn a lot more about this.
For now, we have done part of the hard work for you with the following functions present in Expression.hs:
Exercise 10
Your task is to write a function eval that will evaluate such expressions, as in:
so that you can evaluate strings which correspond to arithmetical expressions:
The idea will be to break the problem into handy parts. For instance, if a token list starts with: [Num x, op, Num y, opNext, …] we could simplify the job by evaluating the `rst bit ([Num x, op, Num y]) so that it will become a single number, and then re-evaluating the now smaller list [Num (x op y), opNext, …]. If we keep doing this, will this eventually result in a single number? When might it not work?
Start implementing your eval function and see how far you get. We recommend the following steps:
1. Determine the type signature of the function
2. Figure out the shortest lists the function should be able to handle (“base case(s)”) 3. ImplementPlusandMinus
Plus and Minus
If you have a function signature (or you want to see what Haskell thinks of your function `rst), then start with the following pattern:
Num x : op : Num y : nextOp : remainingExp
Analyse carefully each element in this pattern. What does it mean? Which variables correspond to what values? What are the types of the individual elements? What length of lists can this pattern match?
Before you lose sleep over what to return, the return value corresponding to the above pattern is as follows:
eval ((eval [Num x, op, Num y]) ++ nextOp : remainingExp)
We are breaking down the evaluation of the whole list into the two problems:
1. The `rst operator 2. The smaller list
You will need to handle the shorter case that we just used in the result, of course, which is [Num x, op, Num y]. Make sure you understand what this pattern could match, too, and use a second case expression inside the main one to solve it for each op.
Test your eval function on something simple with Plus and Minus in it, without any negative numbers:
eval [Num 3.0, Minus, Num 1.0, Minus, Num 1.0, Minus, Num 1.0]
Negative Numbers
With the above exercise complete, we can now work on negative numbers. The tokeniser does not link minus signs to numbers, since we only have the single token Minus for both negation and subtraction. Consider the following expression:
[Num 3.1, Plus, Minus, Num 4.2, Minus, Num 5.2, Plus, Num 6.3]
You should write a pattern to match this situation, and the beginning of the list should
translate into:
[Num 3.1, Plus, Num (-4.2), …]
Test your implementation a few times to make sure it works.
More operations
Implement operations with different operator precedence, such as Times, DividedBy and Power. You will need to extend your Token data type.
You will also need to extend the functions tokenise and showExpression to cater for these extra tokens as well.
Order of Operations
Now for the `nal step: operators with different binding power, or precedence. Times, DividedBy are of higher precedence (binding power) than Plus and Minus, and Power has the highest precedence of all.
Consider the expression that we wrote earlier:
eval ((eval [Num x, op, Num y]) ++ nextOp : remainingExp)
This is only correct if the precedence of op is greater than or equal to that of nextOp.
Otherwise, we want to evaluate nextOp `rst, with the following pattern: eval (Num x: op: eval (Num y: nextOp: remainingExp))
You need two things for correct evaluation:
1. A function that gives you the binding power or precedence of an operation (call it bindingPower).
2. A guard to pick the right evaluation depending on the binding power of the two operations (bindingPower op >= bindingPower nextOp)
If you are confused how to add a guard to a case expression, there is an example in the code for tokenise. Make sure that bindingPower returns larger values for Power than Times and DividedBy, and that those are in turn larger than Plus and Minus.
After you add the guards to the right place in your eval function, your function will be complete! You should now be able to evaluate any valid expression based on the given tokens. Check this carefully by testing against meaningful examples that you have developed through black box and white box testing.
References
1. Haddock: A Haskell Documentation Tool https://haskell- haddock.readthedocs.io/en/latest/index.html
2. Haskell Style Guide https://cs.anu.edu.au/courses/comp1100/resources/01- style/
3. Haskell Style Guide by Johan Tibbel https://github.com/tibbe/haskell-style- guide/blob/master/haskell-style.md
This lab contains additional exercises for COMP1130 students, which are optional but encouraged for COMP1100 students. Make sure that you submit attempts at all exercises required for your course in order to receive full participation marks. The deadline for this is the start of your next lab.
In the following sections, the symbol means that you should replace the symbol with appropriate text, such as a module name, function name etc.
In this section, let us assume we have an online library database that stores videos: movies and shows along with their availability.
{-|
Module :
Description : Maintainer :

-}
module where …
Create a module (in VSCodium, create a new `le) named Library.hs. (Does this obey all the naming rules? If the name does not obey the rules, modify it.)
Add the module level documentation, following the rules and template provided above.
— | This is the documentation for the datatype.
data T
= C1 a b — ^ This is the documentation for the ‘C1’ constructor | C2 a b — ^ This is the documentation for the ‘C2’ constructor | …
type Name = String
type Year = Int
type Availability = Bool
Create a datatype for a video named Video with two constructors Movie and Show. Each constructor should have two `elds Name and Year. Follow the style guideline above and write documentation for the datatype and the constructor `elds.
library :: Library library =
[ (Show “Westworld” 2017, False)
, (Movie “Harry Potter and the Prisoner of Azkaban” 2004, False)
, (Show “Game of Thrones” 2011, True)
, (Movie “Thor: Ragnarok” 2017, False)
, (Movie “Avengers: Endgame” 2019, False)
, (Show “Attack on Titan” 2009, True)
, (Show “Stranger Things” 2016, False)
, (Movie “Star Wars: The Force Awakens” 2015, True)
, (Show “The Walking Dead” 2010, True)
, (Movie “Deadpool” 2016, True) ]
lengthList :: [a] -> Int lengthList list = case list of
[] ->0
_:xs -> 1 + lengthList xs
lengthList list = case list of [] ->0
_:xs -> 1 + lengthList xs
— | The ‘find’ function checks if a given element is inside a list.
find :: Integer -> [Integer] -> Bool find elem list = case list of
[] -> False
x:xs -> x == elem || find elem xs
— | This function increments its argument inc :: Integer -> Integer
incint= int+1
Using the guidelines outlined above, de`ne a function, using an appropriate name, that uses the name of a video to check whether a movie or a show is available in a given library.
Using all the guidelines outlined above, de`ne a function, using an appropriate name, that takes a library and returns a list of available videos. The function should return an empty list if none of the videos in the input library is available or if the library is empty.
In the provided Haskell module BoxTesting.hs, we will be writing a function that `nds the second smallest value in a list of Int, if there is one.
After you have thought of as many instances of black box tests as you think you need, write these tests down as doctests. Please re-visit Lab03 if you are unsure how to do this.
Ensure you have followed the style guidelines discussed in the `rst section of the lab.
Write white box tests as needed (there is no need to repeat testing groups already covered by your black tests). Check that your program passes all tests. Use a comment to clearly label the separation between your black box and white box tests, so that your tutor can verify that you have completed both exercises.
Add some tests to the functions isAvailable and availableVids in the Library.hs module from previous section if you have not done so already.
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.
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.
type Expression = [Token]
data Token = Plus | Minus | Num Double
deriving (Show, Eq)
tokenise :: String -> Expression showExpression :: Expression -> String evalStringExpression :: String -> String
>>> eval [Num 3.2, Minus, Num 4.2, Minus, Num 5.3, Plus, Num 6.3] [Num 0.0]
>>> evalStringExpression “3.2 – 4.2 – 5.3 + 6.3” “0.0”
In this simpli`ed version of this problem, we will work only with non-negative numbers, so that we do not have to deal with the unary minus operator, as in expressions such as 3.2 + (-4.2) – 5.3 where (-) is used as both a unary and a binary operator.
Make sure you follow the style and testing guidelines provided early in the lab throughout the design of eval and any helper functions.
data Token = Plus | Minus | Times | DividedBy | Power | Num Double deriving (Show, Eq)
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