Programming Assignment #4 (Haskell)
CS671
due 3 July 2020 11:59pm
1 Representing Dates
Create functionality for a data type to represent calendar dates. Your dates should be able to represent any
valid calendar date (January 1st through December 31st for any year.) You should allow for “leap days”
(February 29th), with leap days in years divisble by 4, except those years which are divisible by 100 and
not by 400 (ie. 2100, 2200, and 2300 have no leap day, but 2400 does.) The three Int values represent day,
month, and year in that exact order.
data Date = NoDate | Date Int Int Int deriving Eq
ˆ Write a function makeDate which takes day, month, and year (all Int) as inputs and generates a Date
value. If the inputs represent a valid calendar date, then return a Date value with those numbers for
the day, month, and year. If the inputs do not represent a valid calendar date, return NoDate. 10 pts
ˆ Create an instance of Show Date that makes Date values be displayed in month/day/year format, such
as 12/31/2020. NoDate values should be displayed as “Not a valid date”. 10 pts
ˆ Write a function nextDate which takes a Date as input and returns the next calendar date. If given
NoDate, it should return NoDate. 10 pts
ˆ Write a function prevDate which takes a Date as input and returns the previous calendar date. If
given NoDate, it should return NoDate. 10 pts
ˆ Write a function before which takes two Date values as inputs. It returns True if the first date comes
before the second chronologically and False otherwise. It should return False if either input is NoDate. 5 pts
ˆ Write a function after which takes two Date values as inputs. It returns True if the first date comes
after the second chronologically and False otherwise. It should return False if either input is NoDate. 5 pts
2 Evaluating Expressions
Use the Stack type defined below to evaluate expressions given in postfix notation. You will process one
“token” (separated by spaces) from the expression at a time. If the current token is an operand (represents
an integer), then you should push it onto the stack of operands. If the token is an operator (+, -, *, /), then
you should pop two operands from the stack, do the operation with those operands, and push the result onto
the stack. When you reach the end of the expression, there should be one value left on the stack and that
value is the result of the expression.
data Stack a = EmptyStack | Item a (Stack a) deriving Show
push x EmptyStack = Item x EmptyStack
push x s = Item x s
top (Item x _) = x
pop (Item _ t) = t
size EmptyStack = 0
size (Item _ s) = 1 + size s
1
ˆ Make a function eval which takes a string as input, where the string contains a postfix expression.
It should process the expression token by token as described above. If the expression is invalid (such
as having too many or too few operands), the function should return Nothing. If the expression is
valid, the function should return a Just with the result. For example, eval “3 5 + 2 -” should result
in Just 6 and eval “2 +” should result in Nothing. You can assume that all tokens in the string
represent either an integer or an operand. 20 pts
3 Backtracking to Make Change
We consider the problem of giving change using coins and bills from a cash register. We model coins and
bills as integers and the cash register as a list of positive integers (possibly with duplicates.) The problem
becomes one of finding in a given list a sublist of integers that add up to a given target. The simplest
algorithm to solve this problem is described below. You may want to add some optimizations to it, but it
can be a useful starting place.
Given a list of integers L and a target amount t:
ˆ If the t is zero, the problem is trivially solved with an empty list.
ˆ Otherwise, if the list L is empty, the problem has no solution and the algorithm fails.
ˆ Otherwise, pick a number x from L and let L
0 be the list of remaining numbers from L after x is
removed. If x is larger than t, it is certainly unusable (since all numbers are positive). Discard it and
try to make change for t with L
0
through a recursive call. If x is not larger than t, we can try to use
it. So, try to make change for t − x with L
0 using a recursive call.
– If this succeeds, we have a list of integers from L
0
that add up to t − x. Add x to that list to get
a list of integers from L that add up to x, which is a solution to the original problem.
– Otherwise, if the algorithm fails to make change for t − x with L
0
, it means that x shouldn’t be
used. Discard it and try to make change for t with L
0 using a recursive call.
This algorithm uses a programming technique known as backtracking: try something and, if it doesnt
work, backtrack and try something else. In this case, the choice is between two branches: to use x or not. In
order to implement backtracking, we need a way for the program to fail and to continue after failure. You
can do this in Haskell by using the Maybe type, where a failure results in Nothing and if a result such as
[5,10,10,25] is found, the result will be Just [5,10,10,25].
ˆ Write a function makeChange which takes a list of Int values and an Int as input. It should implement
the above algorithm (with any optimizations you choose) resulting in a list of Int values which represent
change made for the input amount from the cash register (the input list.) For example: 30 pts
makeChange [4,2,32,5,7,1,33,4,1,6] 41 may result in Just [4,2,1,33,1]
(or some other combination of numbers from the list that add up to 41), while
makeChange [4,2,32,5,7,1,33,4,1,6] 64 should result in Nothing
2
Notes:
ˆ This assignment must be submitted in a file named HW4.hs that declares a module named HW4. This
file can load other files using import, if necessary. Make sure to submit any such files along with
HW4.hs for grading.
ˆ You will want to split the string for eval into a list. One of the ways to split a string is the
Data.List.Split library’s splitOn function.
ˆ To convert a string to an integer, you can use the read function, such as read x::Int.
ˆ Recursive functions dont have to be tail recursive. You should, however, work toward efficient implementations that will handle larger values than what is shown in the sample tests.
ˆ Do not derive from more types than what is listed for the types you define. Relying on funcitonality
other than what is defined in the assignment may cause you to fail the tests.
ˆ Functions can use previously defined functions, as well as other intermediate functions that are not
part of the assignment. It is not required to hide intermediate functions in let and where blocks.
ˆ Functions dont have to use pattern matching or guards. In particular, functions that work on lists
can be written using head, tail, null, etc. However, pattern matching or guards will probably greatly
improve your code.
ˆ Functions must have the following types:
makeDate :: Int -> Int -> Int -> Date
nextDate :: Date -> Date
prevDate :: Date -> Date
before :: Date -> Date -> Bool
after :: Date -> Date -> Bool
eval :: [Char] -> Maybe Int
makeChange :: (Num a, Ord a) => [a] -> a -> Maybe [a]
3