Homework 3: All about Fold Solution

$30.00

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 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]

“`


error: Content is protected !!