# Haskell代写 | CS671 Programming Assignment #4

这个作业是用Haskell创建用于表示日历日期的数据类型的功能

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