Description
Problems
1. commons, commons_tail, and commons_all
(a) commons – 5%
The function commons takes two lists, l1 and l2, and returns a list including the elements that exists
in both lists. The resulting list should not include any duplicates. The elements in the output can have
arbitrary order.
You may use the built in elem function in your solution.
The type of commons should be compatible with the following :
commons :: Eq a => [a] -> [a] -> [a]
Examples:
> commons [2,2,5,6,6,8,9] [1,3,2,2,4,4,5,7,8,10]
[2,5,8]
> commons [5,6,7,8,9] [8,8,10,10,11,12,5]
[5,8]
> commons [“a”,”b”,”d”] [“c”,”e”,”f”,”g”]
[]
> commons [1,2,3] []
[]
(b) commons_tail – 9%
Re-write the commons function from part (a) as a tail-recursive function. Name your function
commons_tail.
The type of commons_tail should also be Eq a => [a] -> [a] -> [a]
You may use the same test cases provided above to test your function.
(c) commons_all – 3%
Using commons function defined above and the foldr (or foldl) function, define
commons_all which takes a list of lists and returns a list containing the common elements from all the
sublists of the input list. Provide an answer using foldr (or foldl); without using explicit recursion.
The type of commons_all should be compatible with the following:
commons_all:: Eq a => [[a]] -> [a]
Examples:
> commons_all [[1,3,3,4,5,5,6],[3,4,5],[4,4,5,6],[3,5,6,6,7,8]]
[5]
> commons_all [[3,4],[-3,-4,3,4],[-3,-4,5,6]]
[ ]
> commons_all [[3,4,5,5,6],[4,5,6],[],[3,4,5]]
[ ]
2. find_courses and max_count
Assume the “progLanguages” data we used in HW1.
progLanguages =
[ (“CptS121” , [“C”]),
(“CptS122” , [“C++”]),
(“CptS223” , [“C++”]),
(“CptS233” , [“Java”]),
(“CptS321” , [“C#”,”Java”]),
(“CptS322” , [“Python”,”JavaScript”]),
(“CptS355” , [“Haskell”, “Python”, “PostScript”, “Java”]),
(“CptS360” , [“C”]),
(“CptS370” , [“Java”]),
(“CptS315” , [“Python”]),
(“CptS411” , [“C”, “C++”]),
(“CptS451” , [“Python”, “C#”, “SQL”,”Java”]),
(“CptS475” , [“Python”, “R”])
]
(a) find_languages – 10%
Write a Haskell function find_languages that takes the list of courses (similar to progLanguages)
and a list of course names (for example [“CptS451”, “CptS321”, “CptS355”]) as input and returns
the common languages used by all courses in the course list.
Your function shouldn’t need a recursion but should use higher order functions (map, foldr/foldl,
or filter). Your helper functions should not be recursive as well, but they can use higher order
functions.
Hint: You can use the commons_all function you defined in problem 1.
The type of the find_languages function should be compatible with the following:
find_languages::(Eq a1, Eq a2) => [(a2, [a1])] -> [a2] -> [a1]
Examples:
> find_languages progLanguages [“CptS451”, “CptS321”, “CptS355”]
[“Java”]
> find_languages progLanguages [“CptS451”, “CptS321”, “CptS355″,”CptS411”]
[ ]
> find_languages progLanguages [“CptS451”, “CptS322”, “CptS355″,”CptS475”]
[“Python”]
(b) find_courses – 12%
Write a Haskell function find_courses that takes the list of courses (similar to progLanguages) and a
list of programming language names (for example [“Python”,”C”,”C++”]) as input and returns a list of
tuples where each tuple pairs the programming languages with the list of courses that use that
programming language.
Your function shouldn’t need a recursion but should use higher order functions (map, foldr/foldl,
or filter). Your helper functions should not be recursive as well, but they can use higher order
functions.
The type of the find_courses function should be compatible with the following:
find_courses :: Eq t1 => [(a, [t1])] -> [t1] -> [(t1,[a])]
Examples:
> find_courses progLanguages [“Python”,”C”,”C++”]
[(“Python”,[“CptS322″,”CptS355″,”CptS315″,”CptS451″,”CptS475”]),(“C”,
[“CptS121″,”CptS360″,”CptS411”]),(“C++”,[“CptS122″,”CptS223″,”CptS411”])]
> find_courses progLanguages [“Java”,”Go”,”R”]
[(“Java”,[“CptS233″,”CptS321″,”CptS355″,”CptS370″,”CptS451”]),(“Go”,[]),
(“R”,[“CptS475”])]
3. nested_max, max_maybe, and max_numbers
(a) nested_max – 2%
Function nested_max is given a list of lists and it returns the maximum of all numbers in all
sublists of the input list. Your function shouldn’t need a recursion but should use functions “map” and
“foldr”. You may define additional helper functions which are not recursive.
The type of the nested_max function should be compatible with the following:
nested_max :: [[Int]] -> Int
If the list is empty, you should return (minBound::Int) value
Examples:
> nested_max [[1,2,3],[4,5],[6,7,8,9],[]]
9
> nested_max [[10,10],[10,10,10],[10]]
10
> nested_max [[-1,-2,-3],[-4,0,-5],[-6,0,-7,0,-8,-9],[]]
0
(b) max_maybe – 8%
Function max_maybe is given a list of Maybe lists and it returns the maximum of all Maybe
values in all sublists of the input list. Your function shouldn’t need a recursion but should use functions
“map” and “foldr”. You may define additional helper functions which are not recursive. The type
of the max_maybe function should be compatible with the following:
max_maybe :: Ord a => [[Maybe a]] -> Maybe a
(Note: To implement max_maybe, change your nested_max function and your helper function in
order to handle Maybe values instead of Int’s. Assume Nothing is smaller than any Just value.)
Examples:
> max_maybe [[(Just 1),(Just 2),(Just 10),(Just 3)],[(Just 4),(Just
5)],[(Just 6),(Just 10),Nothing ],[],[Nothing ]]
Just 10
> max_maybe [[(Just “A”),Nothing],[(Just “X”), (Just “B”), (Just
“Z”),Nothing,Nothing]
Just “Z”
> max_maybe [[Nothing ]]
Nothing
> max_maybe []
Nothing
(c) max_numbers – 8%
Define the following Haskell datatype:
data Numbers = StrNumber String | IntNumber Int
deriving (Show, Read, Eq)
Define a Haskell function max_numbers that takes a nested list of Numbers values and it returns the
maximum value (as an Int) among all Numbers in all sublists of the input list. The parameter of the
StrNumber values should be converted to integer and included in the comparison. You may use the
following function to convert a string value to integer.
getInt x = read x::Int
Your max_numbers function shouldn’t need a recursion but should use functions “map” and
“foldr”. You may define additional helper functions which are not recursive. The type of the
max_numbers function should be compatible with the following:
max_numbers :: [[Numbers]] -> Int
If the list is empty, you should return (minBound::Int) value.
Examples:
> max_numbers [[StrNumber “9”,IntNumber 2,IntNumber 8],[StrNumber “4”,IntNumber
5],[IntNumber 6,StrNumber “7”],[],[StrNumber “8”]]
9
> max_numbers [[StrNumber “10” , IntNumber 12],[],[StrNumber “10”],[]]
12
> max_numbers [[]]
-9223372036854775808 (minBound value)
4. tree_scan, tree_search, merge_trees
In Haskell, a polymorphic binary tree type with data both at the leaves and interior nodes might be
represented as follows:
data Tree a = LEAF a | NODE a (Tree a) (Tree a)
deriving (Show, Read, Eq)
(a) tree_scan – 5%
Write a function tree_scan that takes a tree of type (Tree a) and returns a list of the a values
stored in the leaves and the nodes. The order of the elements in the output list should be based on the
“InOrder” traversal of the tree.
The type of the tree_scan function should be: tree_scan :: Tree a -> [a]
Examples:
t1 = NODE
“Computer”
(NODE “of” (LEAF “School”)(NODE
“Engineering”
(LEAF “Electrical”)
(LEAF “and”)))
(LEAF “Science”)
tree_scan t1
[“School”,”of”,”Electrical”,”Engineering”,”and”,”Computer”,”Science”]
t2 = NODE 1 (NODE 2 (NODE 3 (LEAF 4) (LEAF 5)) (LEAF 6)) (NODE 7 (LEAF 8) (LEAF 9))
tree_scan t2
[4,3,5,2,6,1,8,7,9]
tree_scan (LEAF 4)
[4]
(b) tree_search – 12%
Write a function tree_search that takes a tree of type (Tree a) and a value and returns the level of
the tree where the value is found. If the value doesn’t exist in the tree, it returns -1. The tree nodes
should be visited with “InOrder” traversal and the level of the first matching node should be returned.
The type of the tree_search function should be compatible with the following:
tree_search :: (Ord p, Num p, Eq a) => Tree a -> a -> p
4 5
6 8 9
1
3
2 7
[4,5,3,6,2,8,9,7,1
]
InOrder traversal of the tree:
[4,3,5,2,6,1,8,7,9]
t3 = NODE 8 (NODE 2 (NODE 3 (LEAF 2) (LEAF 5)) (LEAF 1)) (NODE 1 (LEAF 8) (LEAF 5))
tree_search t3 1
3
tree_search t3 5
4
tree_search t3 8
1
tree_search t3 4
-1
(c) merge_trees – 14%
Write a function merge_trees that takes two (Tree int) values and returns an (Tree int)
where the corresponding nodes from the two trees are added. The trees might have different depth.
You should copy particular branches/nodes of the trees if the other tree doesn’t have that branch/node.
See the example below.
The type of the merge_trees function should be compatible with the following:
merge_trees :: Num a => Tree a -> Tree a -> Tree a
We can create the above Tree(s) as follows:
left :
left = NODE 1 (NODE 2 (NODE 3 (LEAF 4) (LEAF 5)) (LEAF 6)) (NODE 7 (LEAF 8) (LEAF 9))
right:
right = NODE 1 (NODE 2 (LEAF 3) (LEAF 6)) (NODE 7 (NODE 8 (LEAF 10) (LEAF 11)) (LEAF 9))
And merge_trees left right will return the rightmost (Tree Int) which is equivalent to
the following:
NODE 2
(NODE 4 (NODE 6 (LEAF 4) (LEAF 5)) (LEAF 12))
(NODE 14 (NODE 16 (LEAF 10) (LEAF 11)) (LEAF 18))
2 5
1 8 5
8
3
2 1
Level 1
Level 2
Level 3
Level 4
4 5
6 8 9
1
3
2 7
10 11
6 8 9
1
3
2 7
4 5
12 16 18
2
6
4 14
10 11
+ =
5. Tree examples – 3%
Create two trees of type Tree. The height of both trees should be at least 4. Test your functions
tree_scan, tree_search, merge_trees with those trees. The trees you define should be
different than those that are given.
Include your example trees in HW2Tests.hs file under the comment “INCLUDE YOUR TREE
EXAMPLES HERE”. Do not include your sample tests in HW2.hs.
Assignment rules – 4%
Make sure that your assignment submission complies with the following. :
– The module name of your HW2.hs files should be HW2. Please don’t change the module name in
your submission file.
– The function names in your solutions should match the names in the assignment prompt. Running
the given tests will help you identify typos in function names.
– Make sure to remove all test data from the HW2.hs file, e.g. , tree examples provided in the
assignment prompt , the test files and the ‘progLanguages‘ list for Problem-2.
– Make sure to include your own tree values in HW2Tests.hs file.
– Make sure to define your helper functions inside a let..in or where block.
Testing your functions – 5%
The HW2SampleTests.zip file includes 6 .hs files where each one includes the HUnit tests for a
different HW problem. The tests compare the actual output to the expected (correct) output and raise
an exception if they don’t match. The test files import the HW2 module (HW2.hs file) which will include
your implementations of the HW problems.
You will write your solutions to HW2.hs file. To test your solution for each HW problem run the
following commands on the command line window (i.e., terminal):
$ ghci
$ :l P1_HW2tests.hs
P1_HW2tests> run
Repeat the above for other HW problems by changing the test file name, i.e. , P2_HW2tests.hs,
P3_HW2tests.hs, etc.
You are expected to add at least 2 more test cases for each problem. Write your tests for all problems
in HW2_tests.hs file – the template of this file is provided to you in the HW2 assignment page. Make
sure that your test inputs cover all boundary cases. Also, your test inputs should not be same or very
similar to the given sample tests.
Note : For problem 4(abc), you can use the trees you created in problem-5. See above.
To run your own test file run the following command on the GHCI prompt:
$ :l HW1tests.hs
HW1tests> run
If you don’t add new test cases or if your tests are very similar to the given tests, you will be deduced 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
