CptS355 – Assignment 2 (Haskell) Spring 2021
Assigned: Thursday, February 25, 2021
Due: Friday, March 5, 2021
Weight: Assignment 2 will count for 8% of your course grade.
Your solutions to the assignment problems are to be your own work. Refer to the course academic integrity statement in the syllabus.
This assignment provides experience in Haskell programming. Please compile and run your code on command line using Haskell GHC compiler. You may download GHC at https://www.haskell.org/platform/.
Turning in your assignment
The problem solution will consist of a sequence of function definitions and unit tests for those functions. You will write all your functions in the attached HW2.hs file. You can edit this file and write code using any source code editor (Notepad++, Sublime, Visual Studio Code, etc.). We recommend you to use Visual Studio Code, since it has better support for Haskell.
In addition, you will write unit tests using HUnit testing package. Attached file, HW2SampleTests.hs, includes at least one test case for each problem. You will edit this file and provide additional tests for problems 3(b,c) and 4(a,b,c) (at least 2 tests per function). Please use test input different than those provided in the assignment prompt. Rename your test file as HW2Tests.hs.
To submit your assignment, please upload both files (HW2.hs and HW2Tests.hs) on the Assignment2 (Haskell) DROPBOX on Canvas (under Assignments).
The work you turn in is to be your own personal work. You may not copy another student’s code or work together on writing code. You may not copy code from the web, or anything else that lets you avoid solving the problems for yourself. At the top of the file in a comment, please include your name and the names of the students with whom you discussed any of the problems in this homework. This is an individual assignment and the final writing in the submitted file should be *solely yours*.
Important rules
• Unless directed otherwise, you must implement your functions using the basic built-in functions in the Prelude library. (You are not allowed to import an additional library and use functions from there.)
• If a problem asks for a non-recursive solution, then your function should make use of the higher order functions we covered in class (map, foldr/foldl, or filter.) For those problems, your main functions can’t be recursive. If needed, you may define non-recursive helper functions.
• Make sure that your function names match the function names specified in the assignment specification. Also, make sure that your functions work with the given tests. However, the given test inputs don’t cover all boundary cases. You should generate other test cases covering the extremes of the input domain, e.g. maximum, minimum, just inside/outside boundaries, typical values, and error values.
• Question 1(b) requires the solution to be tail recursive. Make sure that your function is tail recursive otherwise you won’t earn points for this problem.
• You will call foldr/foldl, map, or filter in several problems. You can use the built-in definitions of these functions.
• When auxiliary/helper functions are needed, make them local functions (inside a let..in or where blocks). You will be deducted points if you don’t define the helper functions inside a let..in or where block. If you are calling a helper function in more than one function, you can define it in the main scope of your program, rather than redefining it in the let blocks of each calling function.
• Be careful about the indentation. The major rule is “code which is part of some statement should be indented further in than the beginning of that expression”. Also, “if a block has multiple statements, all those statements should have the same indentation”. Refer to the following link for more information: https://en.wikibooks.org/wiki/Haskell/Indentation
• Haskell comments : — line comment
Problems
1. longest, longestTail, and mergeN – 20%
(a) longest – 5%
The function longest takes a nested list (i.e., list of lists) as input and returns the longest sublist in that nested list. The type of longest should be compatible with: longest :: [[a]] -> [a] Hint: Implement a helper function that will return the longer of the two given lists and use it in your solution. Examples:
> longest [[1],[5,7],[1,2,3],[7,8,9,10]]
[7,8,9,10]
> longest [“which”,”of”,”these”,”words”,”is”,”the”,”longest”,”?”]
“longest”
> longest []
[]
(b) longestTail – 10%
Re-write the longest function from part (a) as a tail-recursive function. Name your function longestTail. The type of longestTail should be compatible with:
longestTail :: [[a]] -> [a]
Examples:
> longestTail [[1],[5,7],[1,2,3],[7,8,9,10]]
[7,8,9,10]
> longestTail [“which”,”of”,”these”,”words”,”is”,”the”,”longest”,”?”] “longest”
> longestTail []
[]
(c) mylongest – 5%
Re-write your longest function using higher order functions (map, foldr/foldl, or filter) ; without using explicit recursion. The type of longestTail should be compatible with: longestTail :: [[a]] -> [a] Examples:
> mylongest [[1],[5,7],[1,2,3],[7,8,9,10]]
[7,8,9,10]
{- multi line comment-}.
> mylongest [“which”,”of”,”these”,”words”,”is”,”the”,”longest”,”?”] “longest”
> mylongest []
[]
2. getMonths and monthlyCans – 20%
Consider the feeding log data you used in HW1 . Recall that this list includes tuples where the first value in each tuple is the timestamp representing a month and the second value is the feeding log for that month.
myCatsLog=[((7,2020),[(“Oceanfish”,7),(“Tuna”,1),(“Whitefish”,3),(“Chicken”,4),(“Beef”,2)]),
((8,2020),[(“Oceanfish”,6),(“Tuna”,2),(“Whitefish”,1),(“Salmon”,3),(“Chicken”,6)]),
((9,2020),[(“Tuna”,3),(“Whitefish”,3),(“Salmon”,2),(“Chicken”,5),(“Beef”,2),(“Turkey”,1),(“Sardines”,1)]),
((10,2020),[(“Whitefish”,5),(“Sardines”,3),(“Chicken”,7),(“Beef”,3)]),
((11,2020),[(“Oceanfish”,3),(“Tuna”,2),(“Whitefish”,2),(“Salmon”,2),(“Chicken”,4),(“Beef”,2),(“Turkey”,1)]),
((12,2020),[(“Tuna”,2),(“Whitefish”,2),(“Salmon”,2),(“Chicken”,4),(“Beef”,2),(“Turkey”,4),(“Sardines”,1)]),
((1,2021),[(“Chicken”,7),(“Beef”,3),(“Turkey”,4),(“Whitefish”,1),(“Sardines”,2)]) ]
(a) getMonths – 10%
getMonths :: (Ord t1, Eq t2) =>[(a, [(t2, t1)])] -> t1 -> t2 -> [a] getMonths :: (Ord t1, Eq t2) =>[((a, b), [(t2, t1)])] -> t1 -> t2 -> [(a, b)] Hint: A possible solution uses “length” function.
Examples:
[(8,2020),(10,2020),(1,2021)]
(b) monthlyCans – 10%
Re-write your getMonths function from HW1 using higher-order functions (i.e., map, foldr/foldl, or filter) and without using explicit recursion. Remember that getMonths takes your cat’s food log (similar to the above), a number “n”, and a cat food flavor (e.g., “chicken, “oceanfish”, etc.) as input and returns the list of months whose feeding logs include more than “n” cans of the given flavor.
The order of the tuples in the output can be arbitrary.
The type of getMonths should be compatible with one of the following:
> getMonths myCatsLog 4 “Oceanfish” [(7,2020),(8,2020)]
> getMonths myCatsLog 5 “Chicken”
Define a function monthlyCans, which calculates the number of cans you fed to your cat each month. It takes your cat’s food log (similar to the above) as input and returns a list of tuples where the first element in each tuple is the timestamp ( i.e., (month, year)) , and the second value is the total
number of cans your cat consumed during that month. Your function shouldn’t need a recursion but should use a higher order function (map, foldr/foldl, or filter). Your helper functions should not be recursive as well, but they can use higher order functions. The order of the tuples in the output can be arbitrary. The type of the function should be compatible with one of the following:
monthlyCans :: Num t1 => [(a, [(t2, t1)])] -> [(a, t1)] monthlyCans :: Num t1 => [((a1,a2), [(t2, t1)])] -> [((a1,a2), t1)]
Examples:
> monthlyCans myCatsLog
[((7,2020),17),((8,2020),18),((9,2020),17),((10,2020),18),((11,2020),16),((12 ,2020),17),((1,2021),17)]
3. convert, sumGrades, and organize – 23%
You are asked to write a program that will store and analyze the courses that college students transferred. The grades of transferred courses can be represented using different grading scales:
1. 4 point SCORE (e.g., 4,3,2,1,0)
2. LETTER grades (e.g., A, B, B, D, F)
3. PASS and FAIL grades
You define the following Haskell datatype to represent the grades:
(a) convert – 3%
Function “convert” converts a given a LETTER value to its equivalent SCORE value. For all other Grade values (i.e., PASS, FAIL, or SCORE), it will return the input value unchanged.
For example:
convert (LETTER ‘A’) returns 4
convert (LETTER ‘B’) returns 3
convert (LETTER ‘C’) returns 2
convert (LETTER ‘D’) returns 1
convert (LETTER ‘F’) returns 0
convert PASS returns PASS
convert FAIL returns FAIL
convert (SCORE 10) returns (SCORE 10)
The type of the convert function should be: convert :: Grade -> Grade
(b) sumGrades – 10%
Define a Haskell function sumGrades that takes a list of Grade values and returns the sum of all grades in that list as a SCORE value. You can assume that PASS and FAIL grades has no score. Your sumGrades function shouldn’t need a recursion but should use a higher order function (map, foldr/foldl, or filter). You may define additional non-recursive helper functions. The type of the sumGrades function should be: sumGrades :: [Grade] -> Grade
(Hint: You may filter out PASS and FAIL scores before you sum the grades. )
Examples:
> sumGrades [LETTER ‘A’, PASS , FAIL, SCORE 1, SCORE 2, SCORE 4, FAIL, PASS, LETTER ‘D’,LETTER ‘C’]
SCORE 14
> sumGrades [PASS, FAIL]
SCORE 0
> sumGrades [] SCORE 0
data Grade = LETTER Char | SCORE Int | PASS | FAIL deriving (Show, Eq, Ord)
(c) organize – 10%
Define a Haskell function sumGrades that organizes a list of courses into sublists according the scale of the course grades. The function takes a list of courses where each course is represented as a (String,Grade) tuple and it returns a nested list of (String,Grade) tuples.
Your organize function shouldn’t need a recursion but should use higher order functions. You may define additional helper functions which are not recursive. The type of the organize should be compatible with one of the following: organize :: [(a, Grade)] -> [[(a, Grade)]]
Examples:
[[(“MATH216”,SCORE 1),(“CptS322”,SCORE 4)],
[(“CptS355”,LETTER ‘A’),(“CptS321”,LETTER ‘D’),(“Math171”,LETTER ‘C’)], [(“CptS499”,PASS),(“EE499”,FAIL)]]
> organize [(“CptS499”,PASS) , (“EE499”,FAIL), (“MATH216”,SCORE 1), (“CptS322”,SCORE 4)] [[(“MATH216”,SCORE 1),(“CptS322”,SCORE 4)],[],[(“CptS499”,PASS),(“EE499”,FAIL)]]
> organize [(“CptS355”, LETTER ‘A’), (“CptS321”,LETTER ‘D’),(“Math171”,LETTER ‘C’)] [[],[(“CptS355”,LETTER ‘A’),(“CptS321”,LETTER ‘D’),(“Math171”,LETTER ‘C’)],[]]
4. createLevelTree, listify, isBalanced – 28%
Consider the following type for a binary tree that stores values both at the interior nodes and the leaves:
> organize [(“CptS355”, LETTER ‘A’), (“CptS499”,PASS),(“EE499”,FAIL),(“MATH216”,SCORE 1), (“CptS322”,SCORE 4), (“CptS321”,LETTER ‘D’),(“Math171”,LETTER ‘C’)]
data Tree a = LEAF a | NODE a (Tree a) (Tree a) deriving (Show, Read, Eq)
We now define another binary tree (similar to Tree type) where the interior nodes store the value , the height of its left child branch and the height its right child branch in a tuple.
data LevelTree a = LLEAF a | LNODE (a,Int,Int) (LevelTree a) (LevelTree a) deriving (Show, Read, Eq)
Example:
Tree 1 LevelTree (1,3,2) red value
2 7 (2,2,1) (7,1,1) green height of left bra
3 6 8 9 (3,1,1) 6 8 9 blue height of right bra [4,5,3,6,2,8,9,7,1
45
4]5
nch nch
(a) createLevelTree-12%
Write a recursive function createLevelTree that takes a Tree value as input and turns it to a LevelTree. The function should calculate the heights of the children branches for each interior node.
You can assume that the height of a LEAF is 1. The type of the createLevelTree function should be: createLevelTree :: Tree a -> LevelTree a
Examples:
tree1 = NODE
“grand-grand-mom”
(NODE “grand-mom” (LEAF “aunt”) (NODE
“mom”
(LEAF “me”)
(LEAF “brother”)))
(LEAF “grand-uncle”)
tree2 = NODE 1 (NODE 2 (NODE 3 (LEAF 4) (LEAF 5)) (LEAF 6)) (NODE 7 (LEAF 8) (LEAF 9))
> createLevelTree tree1
LNODE (1,3,2) (LNODE (2,2,1) (LNODE (3,1,1) (LLEAF 4) (LLEAF 5)) (LLEAF 6))
(LNODE (7,1,1) (LLEAF 8) (LLEAF 9)) > createLevelTree tree2
LNODE (“grand-grand-mom”,3,1) (LNODE (“grand-
mom”,1,2) (LLEAF “aunt”) (LNODE (“mom”,1,1) (LLEAF “me”) (LLEAF “brother”))) (LLE AF “grand-uncle”)
(b) listify-6%
Write a recursive function listify that takes a levelTree value and turns it into a list of tuples. Your function should traverse the tree in “pre-order” (i.e., parent, left child, right child) . The type of the listify function should be: listify :: LevelTree a -> [(a, Int, Int)]
For example:
(1,3,2)
(2,2,1) (7,1,1)
(3,1,1) 6 8 45
listify returns :
[(1,3,2),(2,2,1),(3,1,1),(4,0,0),(5,0,0),(6,0,0),
(7,1,1),(8,0,0),(9,0,0)]
9
leveltree1 = LNODE (“grand-grand-mom”,3,1) (LNODE (“grand-
mom”,1,2) (LLEAF “aunt”) (LNODE (“mom”,1,1) (LLEAF “me”) (LLEAF “brother”))) (LLE
AF “grand-uncle”)
leveltree2 = LNODE (1,3,2) (LNODE (2,2,1) (LNODE (3,1,1) (LLEAF 4) (LLEAF 5)) (LL EAF 6)) (LNODE (7,1,1) (LLEAF 8) (LLEAF 9))
> listify leveltree1
[(“grand-grand-mom”,3,1),(“grand-mom”,1,2), (“aunt”,0,0),(“mom”,1,1),(“me”,0,0),(“brother”,0,0),(“grand-uncle”,0,0)]
> listify leveltree2 [(1,3,2),(2,2,1),(3,1,1),(4,0,0),(5,0,0),(6,0,0),(7,1,1),(8,0,0),(9,0,0)]
(c) isBalanced – 10%
Write a recursive function isBalanced that takes a LevelTree and returns True if the tree is balance, and returns False otherwise. A LevelTree is balanced if, for every interior node, the difference between the heights of left and right children are at most 1. Assume that an LLEAF node is always balanced. The type of the isBalanced function should be:
isBalanced :: LevelTree a -> Bool
For example:
(1,3,2)
(2,2,1) (7,1,1)
(3,1,1) 6 8 45
5. Tree examples – 4%
Testing your functions
isBalanced on the left tree returns True.
[4,5,3,6,2,8,9,7,1
]
9
> isBalanced leveltree1 False
> isBalanced leveltree2 True
Create two trees of type Tree. The height of both trees should be at least 4 (including the root). Test
your createLevelTree function with those trees. Then, you can use the LevelTree values it
returns to test the listify and isBalanced functions. The trees you define should be different
than those that are given.
We will be using the HUnit unit testing package in CptS355. See http://hackage.haskell.org/package/HUnit for additional documentation.
The file HW2SampleTests.hs provides at least one sample test case comparing the actual output with the expected (correct) output for each problem. This file imports the HW2 module (HW2.hs file) which will include your implementations of the given problems.
You are expected to add at least 2 more test cases for problems 3 (b,c) and 4 (abc). You don’t need to provide tests for problems 1 and 2. In your tests make sure that your test inputs cover boundary cases.
Choose test input different than those provided in the assignment prompt. For problem 4 tests, you can use the trees your created in problem 5.
In HUnit, you can define a new test case using the TestCase function and the list TestList includes the list of all test that will be run in the test suite. So, make sure to add your new test cases to the TestList list. All tests in TestList will be run through the “runTestTT tests” command.
If you don’t add new test cases you will be deduced at least 5% in this homework.
Important note about negative integer arguments:
In Haskell, the -x, where x is a number, is a special form and it is a prefix (and unary) operator negating an integer value. When you pass a negative number as argument function, you may need to enclose the negative number in parenthesis to make sure that unary (-) is applied to the integer value before it is passed to the function.
For example: foo -5 5 [-10,-5,0,5,10] will give a type error, but
foo (-5) 5 [-10,-5,0,5,10] will work