1. Background
A bag is an abstract data type that is like a set, except that it can contain multiple copies of the same element. We can represent a bag in Haskell by a list of pairs: each pair contains the element, plus a positive integer indicating how many copies of that element are in the bag.
For the purposes of this assignment, we’ll introduce the following (polymorphic) type synonym, which you will need to include near the top of your code:
type Bag a = [(a,Integer)]
Copyright By PowCoder代写 加微信 powcoder
The intention is that (for example) the type Bag Char indicates a bag whose elements are Char values, whereas the type Bag String indicates a bag whose elements are String values. For any Haskell type t, we can have bags whose elements are values of type t.
Bag Invariants
In the problems that follow, you must maintain the following two invariants (that is, if your function’s argument satisfies these properties, then the function’s result should also satisfy these properties):
• Bag Invariant #1 (All Unique): No bag contains two pairs that have the same first component.
Thus [(‘a’,2),(‘x’,5),(‘a’,1)] is not a valid bag (because two pairs contain ‘a’), but [(‘a’,3),(‘x’,5)] is a valid bag.
• Bag Invariant #2 (All Positive): No bag contains a pair with a number smaller than 1. Thus [(‘a’,0),(‘x’,5)] is not a valid bag, but [(‘x’,5)] is a valid bag.
The order in which unique elements appear is unimportant, however: both [(‘a’,3),(‘x’,5)] and [(‘x’,5),(‘a’,3)] are valid bags.
2. Your Problems
Unless specified otherwise, you must provide recursive functions for this task.
1. Define the following Haskell names/variables (they may be useful for testing out subsequent functions):
a. A variable charBag1 of type Bag Char whose value corresponds to a bag containing the following: one
copy of ‘e’, two copies of ‘y’, and one copy of ‘z’
b. A variable charBag2 of type Bag Char whose value corresponds to a bag containing the following: four copies of ‘e’, two copies of ‘y’, three copies of ‘z’, and two copies of ‘j’
c. A variable charBag3 of type Bag Char whose value corresponds to a bag containing the following: three copies of ‘y’ and one copy of ‘j’
d. AvariablestringBag1oftypeBagStringwhosevaluecorrespondstoabagcontainingthefollowing:two copies of “juice”, one copy of “cereal”, three copies of “toothpaste”, and one copy of “soup”
e. A variable nonBag of type [(String,Integer)] whose value violates both of the bag invariants (i.e., All Unique and All Positive)
2. Write a recursive Haskell function totalItems :: Bag a -> Integer such that totalItems bag calculates the total number of items in bag.
• totalItems charBag2 evaluates to 11
3. WritearecursiveHaskellfunction
howMany :: Eq a => a -> Bag a -> Integer
such that howMany item bag calculates the number of copies of item in bag. Examples:
• howMany ‘y’ charBag1 evaluates to 2
• howMany ‘a’ charBag1 evaluates to 0
4. WritearecursiveHaskellfunction
addToBag :: Eq a => a -> Bag a -> Bag a
such that addBag item bag creates the bag obtained from bag by adding one additional copy of item.
Make sure that the result satisfies the bag invariants.
• addToBag ‘y’ charBag1 produces a bag that has one copy of ‘e’, three copies of ‘y’, and one copy of ‘z’
• addToBag ‘?’ charBag1 produces a bag that has one copy of ‘e’, two copies of ‘y’, one copy of ‘z’, and one copy of ‘?’
5. WritearecursiveHaskellfunction removeFromBag :: Eq a => a -> Bag a -> Bag a
such that removeFromBag item bag creates the bag obtained by removing one copy of item from bag.
Make sure that the result satisfies the bag invariants.
• removeFromBag ‘y’ charBag1 produces a bag that looks like charBag1 except that it contains only one copy of ‘y’
• removeFromBag ‘z’ charBag1 produces a bag that has one copy of ‘e’ and two copies of ‘y’
6. WritearecursiveHaskellfunction
createBagFrom :: String -> Bag Char such that createBagFrom str creates a bag that contains all of the characters from str.
• createBagFrom “hi there!” produces a bag that contains two copies of ‘h’, two copies of ‘e’, and one copy of each of the characters ‘i’, ‘ ‘ , ‘t’ , ‘r’ , and ‘!’.
7. One bag is a sub-bag of a second bag provided that the second bag contains at least as many copies of each item as the first bag. For example, charBag1 is a sub-bag of charBag2 (every item in charBag1 shows up in charBag2 with at least as many copies), but charBag3 is not a sub-bag of charBag2 (charBag3 has more copies of ‘y’ than charBag2).
Write a recursive Haskell function
subBag :: Eq a => Bag a -> Bag a -> Bool
such that subBag bag1 bag2 determines whether bag1 is a subbag of bag2.
• subBag charBag1 charBag2 evaluates to True
• subBag charBag3 charBag2 evaluates to False
8. WritearecursiveHaskellfunction validBag :: Eq a => Bag a -> Bool
such that validBag bag determines whether bag satisfies the bag invariants. Examples:
• validBag charBag1 evaluates to True
• validBag nonBag evaluates to False
What to Submit
You should submit a single Haskell file that contains the following:
• A comment with your name and syr.edu email address at the top of the file
• A comment declaring any assistance you received on this programming task or stating that you received no assistance at all (see details on Blackboard)
• Functions should be given the stated names, have correct type signatures, and appear in the order listed in this task writeup
• For each of the requested functions, you should provide:
– A brief comment that describes the purpose of the function (this can be taken from the task description itself)
– The function definition, including the type signature
– Specific test cases (including ones that are different from the examples I gave!) that can be used to verify the correctness of your function. These tests should be designed before and as you write your code, not as an afterthought.
Briefly explain your rationale for your choice of test cases.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com