Lab 2 (Haskell)

CptS355 - Lab 2 (Haskell) 
Weight: Lab2 will count for 1.5% of your course grade.
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/platforms/.
Turning in your lab submission
This lab involves 7 programming problems and your solution will consist of a sequence of function
definitions for the given problems. You should implement as many of the problems as you can. As
explained in the “Grading” section, 4 correct solutions are sufficient to earn full points in the lab. Note
that some problems have sub-parts; you should complete all parts to get credit for those problems.
You will write all your functions in the attached Lab2.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.
Attached file, Lab2SampleTests.zip, includes HUnit unit tests for each problem. Make sure to
test your code before you submit. Please refer to the “Testing your functions” section at the end of this
document.
To submit your assignment, please upload the file Lab2.hs on the Lab2 (Haskell) DROPBOX on Canvas
(under Assignments). You may turn in your lab submission up to 3 times. Only the last one submitted
will be graded.
Grading
The lab assignments will be auto-graded using automated tests. Your lab grade will be calculated as
follows:
- When you submit the lab, you will automatically earn 60 points.
- For every correct solution that passes all test cases, you will earn 10 points. If your function fails
even a single test case, you will not be able to earn points for that question.
- The lab includes 7 programming problems. You can implement as many of the lab problems as you
want. However, 4 correct answers are sufficient to earn full points (100) in the lab. No extra credit
will be given for additional solutions.
- However, submitting solutions for more than 4 problems will improve your chance to obtain 100%
score (in case one of the test cases fail for the other problems).
- The Lab Zoom sessions are optional. You can work on the lab problems yourself or with your friends
and submit your solutions on Canvas.
Important rules
• In your solutions, you can use any of the built-in Haskell functions included in the lecture notes.
However, you are not allowed to import an external 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 helper functions which are
also not recursive.
• Make sure that the type of your functions match with the type specified in each problem.
• 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.
• 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 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.
Lab Problems
1. merge2, merge2Tail, and mergeN
(a) merge2
The function merge2 takes two lists, l1 and l2, and returns a merged list where the elements from l1
and l2 appear interchangeably. The resulting list should include the leftovers from the longer list and it
may include duplicates.
The type of merge2 should be compatible with merge2 :: [a] -> [a] -> [a].
Examples:
> merge2 [3,2,1,6,5,4] [1,2,3]
[3,1,2,2,1,3,6,5,4]
> merge2 "Ct 5" "pS35"
"CptS 355"
> merge2 [(1,2),(3,4)] [(5,6),(7,8),(9,10)]
[(1,2),(5,6),(3,4),(7,8),(9,10)]
> merge2 [1,2,3] []
[1,2,3]
(b) merge2Tail
Re-write the merge2 function from part (a) as a tail-recursive function. Name your function
merge2Tail.
The type of merge2Tail should be compatible with merge2Tail :: [a] -> [a] -> [a].
You can use reverse or revAppend in your solution. We defined revAppend in class.
(c) mergeN
Using merge2 function defined above and the foldl function, define mergeN which takes a list of
lists and returns a new list containing all the elements in sublists. The sublists should be merged left to
right, i.e., first two lists should be merged first and the merged list should further be merged with the
third list, etc. Provide an answer using foldl; without using explicit recursion.
The type of mergeN should be compatible with : mergeN:: [[a]] -> [a]
Examples:
> mergeN ["ABCDEF","abcd","123456789","+=?$"]
"A+1=a?2$B3b4C5c6D7d8E9F"
> mergeN [[3,4],[-3,-2,-1],[1,2,5,8,9],[10,20,30]]
[3,10,1,20,-3,30,2,4,5,-2,8,-1,9]
> mergeN [[],[],[1,2,3]]
[1,2,3]
2. count and histogram
(a) count
Define a function count which takes a value and a list as input and it count the number of occurrences
of the value in the input list. Your function should not 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. You may use the length function in your implementation.
The type of the count function should be compatible with count :: Eq a => a -> [a] -> Int
Examples:
> count [] [[],[1],[1,2],[]]
2
> count (-5) [1,2,3,4,5,6,7]
0
> count 'i' "incomprehensibilities"
5
(b) histogram
The function histogram creates a histogram for a given list. The histogram will be a list of tuples
(pairs) where the first element in each tuple is an item from the input list and the second element is the
number of occurrences of that item in the list. 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. You may use the count function you defined
in part (a) and eliminateDuplicates function you defined in HW1.
The order of the tuples in the histogram can be arbitrary. The type of the function should be compatible
with histogram :: Eq a => [a] -> [(a, Int)]
Examples:
> histogram [[],[1],[1,2],[1],[],[]]
[([1,2],1),([1],2),([],3)]
> histogram "macadamia"
[('c',1),('d',1),('m',2),('i',1),('a',4)]
> histogram (show 122333444455555)
[('1',1),('2',2),('3',3),('4',4),('5',5)]
3. concatAll, concat2Either, and concat2Str
(a) concatAll
Function concatAll is given a nested list of strings and it returns the concatenation of all
strings in all sublists of the input list. Your function should not need a recursion but should use functions
“map” and “foldr”. You may define additional helper functions which are not recursive.
The type of the concatAll function should be:
concatAll :: [[String]] -> String
Examples:
> concatAll [["enrolled"," ","in"," "],["CptS","-","355"],[" ","and","
"],["CptS","-","322"]]
"enrolled in CptS-355 and CptS-322"
> concatAll [[],[]]
""
(b) concat2Either
Define the following Haskell datatype:
data AnEither = AString String | AnInt Int
 deriving (Show, Read, Eq)
Define a Haskell function concat2Either that takes a nested list of AnEither values and it returns
an AString, which is the concatenation of all values in all sublists of the input list. The parameter of
the AnInt values should be converted to string and included in the concatenated string. You may use
the show function to convert an integer value to a string.
Your concat2Either 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
concat2Either function should be:
concat2Either:: [[AnEither]] -> AnEither
(Note: To implement concat2Either, change your concatAll function and your helper function in
order to handle AnEither values instead of strings.)
Examples:
> concat2Either [[AString "enrolled", AString " ", AString "in", AString " "],[AString
"CptS", AString "-", AnInt 355], [AString " ", AString "and", AString " "], [AString
"CptS", AString "-", AnInt 322]]
AString "enrolled in CptS-355 and CptS-322"
> concat2Either [[AString "", AnInt 0],[]]
AString "0"
> concat2Either []
AString ""
4. concat2Str
Re-define your concat2Either function so that it returns a concatenated string value instead of an
AString value. Similar to concat2Either, the parameter of the AnInt values should be converted
to string and included in the concatenated string.
Your concat2Str 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
concat2Str function should be:
concat2Str:: [[AnEither]] -> String
(Note: To implement concat2Str, change your concat2Either function and your helper function
in order to return a string value instead of an AnEither value.)
> concat2Str [[AString "enrolled", AString " ", AString "in", AString " "],[AString
"CptS", AString "-", AnInt 355], [AString " ", AString "and", AString " "], [AString
"CptS", AString "-", AnInt 322]]
"enrolled in CptS-355 and CptS-322"
> concat2Str [[AString "", AnInt 0],[]]
"0"
> concat2Str []
""
evaluateTree, printInfix, createRTree
Consider the following Haskell type Op that defines the major arithmetic operations on integers.
data Op = Add | Sub | Mul | Pow
 deriving (Show, Read, Eq)
The following function “evaluate” takes an Op value as argument and evaluates the operation on the
integer arguments x and y.
evaluate:: Op -> Int -> Int -> Int
evaluate Add x y = x+y
evaluate Sub x y = x-y
evaluate Mul x y = x*y
evaluate Pow x y = x^y
Now, we define an expression tree as a Haskell polymorphic binary tree type with data at the leaves and
Op operators at the interior nodes:
data ExprTree a = ELEAF a | ENODE Op (ExprTree a) (ExprTree a)
 deriving (Show, Read, Eq)
5. evaluateTree
Write a function evaluateTree that takes a tree of type (ExprTree Int) as input and evaluates
the tree from bottom-up.
The type of the evaluateTree function should be evaluateTree :: ExprTree Int -> Int
For example:
> evaluateTree (ENODE Mul (ENODE Sub (ENODE Add (ELEAF 4) (ELEAF 5)) (ELEAF 6))
 (ENODE Sub (ELEAF 10) (ELEAF 8)))
6
> evaluateTree (ENODE Add (ELEAF 10)
 (ENODE Sub (ELEAF 50) (ENODE Mul (ELEAF 3) (ELEAF 10))))
30
> evaluateTree (ELEAF 4)
4
6. printInfix - 10%
Write a function printInfix that takes a tree of type (ExprTree a) as input and prints the
operands in the interior nodes and the values in the leaf nodes in “in-fix” order to a string. The
expressions lower in the tree are enclosed in parenthesis.
The type of the printInfix function should be:
printInfix:: Show a => ExprTree a -> String
For example:
> printInfix (ENODE Mul (ENODE Sub (ENODE Add (ELEAF 4) (ELEAF 5)) (ELEAF 6))
 (ENODE Sub (ELEAF 10) (ELEAF 8)))
"(((4 `Add` 5) `Sub` 6) `Mul` (10 `Sub` 8))"
> printInfix (ENODE Add (ELEAF 10)
 (ENODE Sub (ELEAF 50) (ENODE Mul (ELEAF 3) (ELEAF 10))))
"(10 `Add` (50 `Sub` (3 `Mul` 10)))"
> printInfix (ELEAF 4)
"4"
4 5
6 10 8
Mul
Add
Sub Sub
evaluateTree on the left tree returns 6.
4 5
6 10 8
Mul
Add
Sub Sub
printInfix on the left tree returns :
"(((4 `Add` 5) `Sub` 6) `Mul` (10 `Sub` 8))"
7. createRTree
Consider the following Haskell tree type.
data ResultTree a = RLEAF a | RNODE a (ResultTree a) (ResultTree a)
 deriving (Show, Read, Eq)
Write a function createRTree that takes a tree of type (ExprTree Int) as input and creates a
tree of type (ResultTree Int). createRTree recursively evaluates each subtree in the input tree
and store the evaluated values in the corresponding nodes in the output ResultTree.
The type of the createRTree function should be:
createRTree :: ExprTree Int -> ResultTree Int
For example:
> createRTree (ENODE Mul (ENODE Sub (ENODE Add (ELEAF 4) (ELEAF 5)) (ELEAF 6))
 (ENODE Sub (ELEAF 10) (ELEAF 8)))
RNODE 6 (RNODE 3 (RNODE 9 (RLEAF 4) (RLEAF 5)) (RLEAF 6)) (RNODE 2 (RLEAF 10) (RLEAF 8))
> createRTree (ENODE Add (ELEAF 10) (ENODE Sub (ELEAF 50) (ENODE Mul (ELEAF 3) (ELEAF 10))))
RNODE 30 (RLEAF 10) (RNODE 20 (RLEAF 50) (RNODE 30 (RLEAF 3) (RLEAF 10)))
> createRTree (ELEAF 4)
RLEAF 4
Testing your functions
The Lab2SampleTests.zip file includes 7 .hs files where each one includes the HUnit tests for a
different lab 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 Lab2 module (Lab2.hs file) which will include
your implementations of the lab problems.
You will write your solutions to Lab2.hs file. To test your solution for the first lab problem run the
following commands on the command line window (i.e., terminal):
$ ghci
$ :l Q1_tests.hs
*Q1_tests> main
Repeat the above for other lab problems by changing the test file name, i.e. , Q2_tests.hs,
Q3_tests.hs, etc.
createRTree on the left tree returns :
4
6 10 8
Mul
Sub Sub
Add
5
[4,5,3,6,2,8,9,7,1
4 ]
6 10 8
6
3 2
9
5
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