-
Notifications
You must be signed in to change notification settings - Fork 8
README
If you wish, this assignment may be completed by groups of two.
To work around ongoing issues with groups in GitHub Classroom, this assignment is configured as an individual assignment rather than as a group assignment, so each person who accepts the assignment on GitHub Classroom will have an individual repository created for them. However, you can still work with a partner if you choose to. In that case, we suggest choosing one partner's repository in which to do all of the group's work, and then adding the other partner as a collaborator to that repository.
To submit your code, first commit and push your repository to GitHub. To see the output of the auto-grader tests, click 'Pull Requests' and select Feedback. You can see the output of the tests under the Checks tab.
When you have completed the assignment, submit your repo to Gradescope by choosing GitHub as the submission method and selecting your repository and the branch containing your completed assignment. Unless you created your own branches, the branch is called 'main'. You can access Gradescope through the Canvas assignment page.
The overall objective of this assignment is to expose you to fold, fold, and more fold. And just when you think you've had enough, FOLD.
Note: To do this assignment, you need to understand how fold works, but you won't have to explicitly call any flavor of fold function in the new code you write; instead, you will fill in the gaps in the provided skeleton code, which itself includes calls to foldLeft. For the problems that do not have calls to foldLeft in the skeleton code, you are not required to use any kind of fold to implement them (although it might be possible to do so).
The homework is in the files:
- src/Hw3.hs has skeleton functions with missing bodies that you will fill in,
- tests/Test.hs has some sample tests, and testing code that you will use to check your assignments before submitting.
You should only need to modify the parts of the files which say:
error "TBD: ..."with suitable Haskell implementations.
Note: Start early, to avoid any unexpected shocks late in the day.
Most of the points will be awarded automatically, by evaluating your functions against a given test suite.
tests/Test.hs contains a very small suite of tests which gives you a flavor of these tests. When you run
$ stack testYour last lines should have
All N tests passed (...)
OVERALL SCORE = ... / ...
or
K out of N tests failed
OVERALL SCORE = ... / ...
If your output does not have one of the above your code will receive a zero
If for some problem, you cannot get the code to compile,
leave it as is with the error ... with your partial
solution enclosed below as a comment.
The other lines will give you a readout for each test. You are encouraged to try to understand the testing code, but you will not be graded on this.
Fill in the skeleton given for sqsum,
which uses foldl' to get a function
sqSum :: [Int] -> Intsuch that sqSum [x1,...,xn] returns the integer x1^2 + ... + xn^2
Your task is to fill in the appropriate values for
- the step function
fand - the base case
base.
Once you have implemented the function, you should get the following behavior:
ghci> sqSum []
0
ghci> sqSum [1, 2, 3, 4]
30
ghci> sqSum [(-1), (-2), (-3), (-4)]
30Fill in the skeleton given for pipe which uses foldl'
to get a function
pipe :: [(a -> a)] -> (a -> a)such that pipe [f1,...,fn] x (where f1,...,fn are functions!)
should return f1(f2(...(fn x))).
Again, your task is to fill in the appropriate values for
- the step function
fand - the base case
base.
Once you have implemented the function, you should get the following behavior:
ghci> pipe [] 3
3
ghci> pipe [(\x -> x+x), (\x -> x + 3)] 3
12
ghci> pipe [(\x -> x * 4), (\x -> x + x)] 3
24Fill in the skeleton given for sepConcat,
which uses foldl' to get a function
sepConcat :: String -> [String] -> StringIntuitively, the call sepConcat sep [s1,...,sn] where
-
sepis a string to be used as a separator, and -
[s1,...,sn]is a list of strings
should behave as follows:
-
sepConcat sep []should return the empty string"", -
sepConcat sep [s]should return just the strings, - otherwise (if there is more than one string) the output
should be the string
s1 ++ sep ++ s2 ++ ... ++ sep ++ sn.
You should only modify the parts of the skeleton consisting
of error "TBD". You will need to define the function f,
and give values for base and l.
Once done, you should get the following behavior:
ghci> sepConcat ", " ["foo", "bar", "baz"]
"foo, bar, baz"
ghci> sepConcat "---" []
""
ghci> sepConcat "" ["a", "b", "c", "d", "e"]
"abcde"
ghci> sepConcat "X" ["hello"]
"hello"Implement the function
stringOfList :: (a -> String) -> [a] -> Stringsuch that stringOfList f [x1,...,xn] should return the string
"[" ++ (f x1) ++ ", " ++ ... ++ (f xn) ++ "]"
This function can be implemented on one line,
without using any recursion by calling
map and sepConcat with appropriate inputs.
You should get the following behavior:
ghci> stringOfList show [1, 2, 3, 4, 5, 6]
"[1, 2, 3, 4, 5, 6]"
ghci> stringOfList (fun x -> x) ["foo"]
"[foo]"
ghci> stringOfList (stringOfList show) [[1, 2, 3], [4, 5], [6], []]
"[[1, 2, 3], [4, 5], [6], []]"The Haskell type Int only contains values up to a certain size. For example,
ghci> let x = 99999999999999999999999999999999999999999999999 :: Int
<interactive>:3:9: Warning:
Literal 99999999999999999999999999999999999999999999999 is out of the Int range -9223372036854775808..9223372036854775807You will now implement functions to manipulate arbitrarily large
numbers represented as [Int], i.e. lists of Int.
Write a function
clone :: a -> Int -> [a]such that clone x n returns a list of n copies of the value x.
If the integer n is 0 or negative, then clone should return
the empty list. You should get the following behavior:
ghci> clone 3 5
[3, 3, 3, 3, 3]
ghci> clone "foo" 2
["foo", "foo"]Use clone to write a function
padZero :: [Int] -> [Int] -> ([Int], [Int])which takes two lists: [x1,...,xn] [y1,...,ym] and
adds zeros in front of the shorter list to make the
list lengths equal.
Your implementation should not be recursive.
You should get the following behavior:
ghci> padZero [9, 9] [1, 0, 0, 2]
([0, 0, 9, 9], [1, 0, 0, 2])
ghci> padZero [1, 0, 0, 2] [9, 9]
([1, 0, 0, 2], [0, 0, 9, 9])Next, write a function
removeZero :: [Int] -> [Int]that takes a list and removes a prefix of leading zeros, yielding the following behavior:
ghci> removeZero [0, 0, 0, 1, 0, 0, 2]
[1, 0, 0, 2]
ghci> removeZero [9, 9]
[9, 9]
ghci> removeZero [0, 0, 0, 0]
[]Let us use the list [d1, d2, ..., dn], where each di
is between 0 and 9, to represent the (positive)
big-integer d1d2...dn.
type BigInt = [Int]For example, [9, 9, 9, 9, 9, 9, 9, 9, 9, 8] represents
the big-integer 9999999998. Fill out the implementation for
bigAdd :: BigInt -> BigInt -> BigIntso that it takes two integer lists, where each integer is
between 0 and 9 and returns the list corresponding to
the addition of the two big-integers. Again, you have to
fill in the implementation to supply the appropriate values
to f, base, args. You should get the following behavior:
ghci> bigAdd [9, 9] [1, 0, 0, 2]
[1, 1, 0, 1]
ghci> bigAdd [9, 9, 9, 9] [9, 9, 9]
[1, 0, 9, 9, 8]Next you will write functions to multiply two big integers. First write a function
mulByInt :: Int -> BigInt -> BigIntwhich takes an integer and a big integer, and returns the big integer list which is the result of multiplying the big integer with the integer. You should get the following behavior:
ghci> mulByInt 9 [9,9,9,9]
[8,9,9,9,1]Now, using mulByInt, fill in the implementation of
bigMul :: BigInt -> BigInt -> BigIntAgain, you have to fill in implementations for f , base , args only.
Once you are done, you should get the following behavior at the prompt:
ghci> bigMul [9,9,9,9] [9,9,9,9]
[9,9,9,8,0,0,0,1]
ghci> bigMul [9,9,9,9,9] [9,9,9,9,9]
[9,9,9,9,8,0,0,0,0,1]