Starting from:
$24
Homework 3: All about Fold Solution
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 homework 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.
**Note:** Start early, to avoid any unexpected shocks late in the day.
## Assignment Testing and Evaluation
Most of 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
$ stack 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
To submit your code, just follow these steps:
1. Go to the src folder and add your homework 3 file:
git add Hw3.hs
2. Commit your changes to your git repository with comments:
git commit -m "Commit Message"
3. Push your changes to your git repository:
git push origin master
4. Upload your latest commit ID in the comment box on canvas.
## 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
```
(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 (fun 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
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`.
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]
[]
```
(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]
```
(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]
```
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 homework 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.
**Note:** Start early, to avoid any unexpected shocks late in the day.
## Assignment Testing and Evaluation
Most of 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
$ stack 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
To submit your code, just follow these steps:
1. Go to the src folder and add your homework 3 file:
git add Hw3.hs
2. Commit your changes to your git repository with comments:
git commit -m "Commit Message"
3. Push your changes to your git repository:
git push origin master
4. Upload your latest commit ID in the comment box on canvas.
## 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
```
(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 (fun 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
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`.
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]
[]
```
(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]
```
(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]
```
1 file (2.6MB)
