Description
Overview
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**.
The assignment is in the files:
1. [src/Hw3.hs](/src/Hw3.hs) has skeleton functions with
missing bodies that you will fill in,
2. [tests/Test.hs](/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:
“`haskell
error “TBD: …”
“`
with suitable Haskell implementations. Do not change the skeleton code,
like `… = foldLeft f base xs`, since the purpose is to get you used to
writing folds.
Exception: you may rename variables that we provide, which includes changing
their patterns. For example, if we give you `(_, res) = …`, feel free to
change it to `(_, result) = …` or `result = …`. Feel free to add guards,
too.
You may also define helper variables in the where clause.
You are allowed to use any library function on integers,
but only the following library functions on lists:
length
append (++)
map
foldl’
foldr
unzip
zip
reverse
If you know the functions `.` (compose) and `$` (apply), feel free to use them,
though they are not by any means necessary to complete this assignment.
**Note:** Start early, to avoid any unexpected shocks late in the day.
Assignment Testing and Evaluation
All the points will be awarded automatically, by
**evaluating your functions against a given test suite**.
[Tests.hs](/tests/Test.hs) contains a very small suite
of tests which gives you a flavor of of these tests.
When you run
“`shell
$ make test
“`
Your 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.
Submission Instructions
Submit your code via the HW-3 assignment on Gradescope.
You must submit a single zip file containing a single directory with your repository inside.
A simple way to create this zip file is:
– Run `git push` to push your local changes to your private fork of the assignment repository
– Navigate to your private fork on github and download source code as a zip
Please *do not* include the `.stack-work` or `__MACOSX` folders into the submission.
**Note:** Upon submission, Gradescope will only test your code on the *small public test suite*,
so it will show maximum 24/160 points.
After the deadline, we will regrade your submission on the full private test suite
and you will get your full points.
Recommended Workflow
Learning folds comes with lots of type errors. You can make certain type errors
less nasty by annotating variables with their types. For example, in the
expression:
“`haskell
f (g x) y
“`
you can annotate any of the variables to prevent the compiler from assigning
them strange types.
“`haskell
f (g x) (y :: Int)
f ((g :: [Int] -> Int) x) y
“`
Additionally, to test the functions that you’ll be writing, we recommend you
run `make ghci`. This brings up a prompt that automatically imports your functions.
Use this prompt to check any of the examples below.
Problem 1: Warm-Up
(a) 15 points
Fill in the skeleton given for `sqsum`,
which uses `foldl’` to get a function
“`haskell
sqSum :: [Int] -> Int
“`
such that `sqSum [x1,…,xn]` returns the integer `x1^2 + … + xn^2`
Your task is to fill in the appropriate values for
1. the step function `f` and
2. the base case `base`.
Once you have implemented the function, you should get
the following behavior:
“`haskell
ghci> sqSum []
0
ghci> sqSum [1, 2, 3, 4]
30
ghci> sqSum [(-1), (-2), (-3), (-4)]
30
“`
(b) 30 points
Fill in the skeleton given for `pipe` which uses `foldl’`
to get a function
“`haskell
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
1. the step function `f` and
2. the base case `base`.
Once you have implemented the function, you should get
the following behavior:
“`haskell
ghci> pipe [] 3
3
ghci> pipe [(\x -> x+x), (\x -> x + 3)] 3
12
ghci> pipe [(\x -> x * 4), (\x -> x + x)] 3
24
“`
**Hint**: if `pipe` throws the error `Couldn’t match type a with a -> a`,
make sure your `f` is returning a function!
(c) 20 points
Fill in the skeleton given for `sepConcat`,
which uses `foldl’` to get a function
“`haskell
sepConcat :: String -> [String] -> String
“`
Intuitively, the call `sepConcat sep [s1,…,sn]` where
* `sep` is 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 string `s`,
* 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:
“`haskell
ghci> sepConcat “, ” [“foo”, “bar”, “baz”]
“foo, bar, baz”
ghci> sepConcat “—” []
“”
ghci> sepConcat “” [“a”, “b”, “c”, “d”, “e”]
“abcde”
ghci> sepConcat “X” [“hello”]
“hello”
“`
(d) 10 points
Implement the function
“`haskell
stringOfList :: (a -> String) -> [a] -> String
“`
such 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:
“`haskell
ghci> stringOfList show [1, 2, 3, 4, 5, 6]
“[1, 2, 3, 4, 5, 6]”
ghci> stringOfList (\x -> x) [“foo”]
“[foo]”
ghci> stringOfList (stringOfList show) [[1, 2, 3], [4, 5], [6], []]
“[[1, 2, 3], [4, 5], [6], []]”
“`
Problem 2: Big Numbers
The Haskell type `Int` only contains values up to a certain size (for reasons
that will become clear as we implement our own compiler). For example,
“`haskell
ghci> let x = 99999999999999999999999999999999999999999999999 :: Int
<interactive>:3:9: Warning:
Literal 99999999999999999999999999999999999999999999999 is out of the Int range -9223372036854775808..9223372036854775807
“`
You will now implement functions to manipulate arbitrarily large
(nonnegative, base-10) numbers represented as `[Int]`, i.e. lists of `Int`.
(a) 10 + 5 + 10 points
Write a function
“`haskell
clone :: a -> Int -> [a]
“`
such that `clone x n` returns a list of `n` copies of the value `x`.
You may use recursion in the implementation of `clone` (though it is
not necessary).
If the integer `n` is `0` or negative, then `clone` should return
the empty list. You should get the following behavior:
“`haskell
ghci> clone 3 5
[3, 3, 3, 3, 3]
ghci> clone “foo” 2
[“foo”, “foo”]
“`
Use `clone` to write a function
“`haskell
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:
“`haskell
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
“`haskell
removeZero :: [Int] -> [Int]
“`
that takes a list and removes a prefix of leading zeros, yielding
the following behavior:
“`haskell
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]
[]
“`
**Note**: you may implement `removeZero` with recursion
(although it is certainly possible with a fold!)
(b) 25 points
Let us use the list `[d1, d2, …, dn]`, where each `di`
is between `0` and `9`, to represent the (positive)
**big-integer** `d1d2…dn`.
“`haskell
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
“`haskell
bigAdd :: BigInt -> BigInt -> BigInt
“`
so 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:
“`haskell
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]
“`
You may find the integer functions `div` and `mod` to be helpful here.
**Note about `BigInt`s**: we expect the result of `bigAdd` to not have any
leading zeroes, like `[0, 1, 0, 9, 9, 8]`. A caveat to this: zero should be
represented as `[]`.
(c) 15 + 20 points
Next you will write functions to multiply two big integers.
First write a function
“`haskell
mulByDigit :: Int -> BigInt -> BigInt
“`
which takes an integer digit and a big integer, and returns the
big integer list which is the result of multiplying the big
integer with the digit. You should get the following behavior:
“`haskell
ghci> mulByDigit 9 [9,9,9,9]
[8,9,9,9,1]
“`
Now, using `mulByDigit`, fill in the implementation of
“`haskell
bigMul :: BigInt -> BigInt -> BigInt
“`
Again, you have to fill in implementations for `f` , `base` , `args` only.
Once you are done, you should get the following behavior at the prompt:
“`haskell
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]
ghci> bigMul [4,3,7,2] [1,6,3,2,9]
[7,1,3,9,0,3,8,8]
ghci> bigMul [9,9,9,9] [0]
[]
“`
