Assignment 3: All about Fold (Points: 24 public / 160 private)

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 has skeleton functions with missing bodies that you will fill in,
2. 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. 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 contains a very small suite of tests which gives you a flavor of of these tests. When you run

$ 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. Connect your Github account to Gradescope and select your repo. If you're in a group, don't forget to add your partner to the submission!

Detailed instructions on how to submit your code directly from the Git repo can be found on Piazza.

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:

f (g x) y

you can annotate any of the variables to prevent the compiler from assigning them strange types.

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 foldLeft to get a function

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:

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

1. the step function f and
2. 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
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 foldLeft to get a function

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:

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

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:

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 example,

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

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

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.

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

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.

Your implementation should not be recursive.

Note about BigInts: we expect the result of bigAdd to not have any leading zeroes, like [0, 1, 0, 9, 9, 8]. The number zero should be represented as [].

(c) 15 + 20 points

Next you will write functions to multiply two big integers. First write a function

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:

ghci> mulByDigit 9 [9,9,9,9]
[8,9,9,9,1]

Your implementation should not be recursive.

Now, using mulByDigit, fill in the implementation of

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:

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

Your implementation should not be recursive.