# Programming Assignment #3 (160 Points)

## Due: Fri, Feb 07, 5:00pm

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 single zip file

```> unzip pa3.zip
```
and out come tumbling several files including
• misc.ml, which contains several skeleton OCaml functions with missing bodies that you will fill in; and
• test.ml which contains some sample tests for you to start with, which you can extend in order to test your implementations more fully.

The file misc.ml contains expressions of the form:

```failwith "..."
```
Your task is to replace the text in those files with the the appropriate OCaml code for each of those expressions.

Note: All the solutions can be done using the purely functional fragment of OCaml, using constructs covered in class, and most require the use of recursion. Solutions using imperative features such as references, while loops or library functions will receive no credit. It is a good idea to start this assignment early; ML programming, while quite simple (when you know how), often seems somewhat foreign at first, particularly when it comes to recursion and list manipulation.

## Assignment Testing and Evaluation

Same as for Assignment #1.

## Submission Instructions

Same steps as in Assignment #1, but this time:

• You need to submit a zipfile with one file, misc.ml:
```> zip firstname_lastname_cse130_pa3.zip misc.ml
```
• You should use `pa3` everywhere instead of `pa1` when running validate_pa3 and turnin.

## Problem #1: Warm-Up

### (A) 15 points

Fill in the skeleton given for sqsum, which uses `List.fold_left` to get an OCaml function

```val sqsum : int list -> int
```
such that `sqsum [x1;...;xn]` returns the integer ```x1^2 + ... + xn^2```

1. the folding function `f` and
2. the base case base

Once you have implemented the function, you should get the following behavior at the OCaml prompt:

```# sqsum [];;
- : int = 0

# sqsum [1;2;3;4];;
- : int = 30

# sqsum [(-1); (-2); (-3); (-4)];;
- : int = 30
```

### (B) 30 points

Fill in the skeleton given for pipe which uses `List.fold_left` to get an OCaml function

```val pipe : (’a -> ’a) list -> (’a -> ’a)
```
such that `pipe [f1;...;fn]` (where `f1`, ... , `fn` are functions!) returns a function `f` such that for any `x`, we have `f x` returns result `fn(...(f2(f1 x)))`.

Again, your task is to fill in the appropriate values for the folding function `f` and the base case base. Once you have implemented the function, you should get the following behavior at the OCaml prompt:
```# pipe [] 3;;
- :  int =  3
# pipe [(fun x -> x+x); (fun x -> x + 3)] 3 ;;
- :  int =  9
# pipe [(fun x -> x + 3);(fun x-> x + x)] 3;;
- :  int =  12
```

### (C) 20 points

Fill in the skeleton given for sepConcat, which uses `List.fold_left` to get an OCaml function
```val sepConcat : string -> string list -> string
```
Intuitively, the expression `sepConcat sep [s1;...;sn]`, where `sep` is a string to be used as a separator, and `[s1;...;sn]` is a list of strings. `sepConcat sep []` should return the empty string `""`. `sepConcat sep [s]` should return just the string `s`. Otherwise, if there are more than one string, in the list, then the output should be the string ```s1 ^ sep ^ s2 ^ ... ^ sep ^ sn```. You should only modify the parts of the skeleton consisting of `failwith "to be implemented"`. You will need to define the function `f`, and give values for `base` and `l`.

Once you have filled in these parts, you should get the following behavior at the OCaml prompt:

```# sepConcat ", " ["foo";"bar";"baz"];;
- : string = "foo, bar, baz"

# sepConcat "---" [];;
- : string = ""

# sepConcat "" ["a";"b";"c";"d";"e"];;
- : string = "abcde"

# sepConcat "X" ["hello"];;
- : string = "hello"
```

### (D) 10 points

Implement the curried OCaml function

```val stringOfList : (’a -> string) -> ’a list -> 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 `List.map` and `sepConcat` with appropriate inputs. Once you have completed this function, you should get the following behavior at the OCaml prompt:

```# stringOfList string_of_int [1;2;3;4;5;6];;
- : string = "[1; 2; 3; 4; 5; 6]"

# stringOfList (fun x -> x) ["foo"];;
- : string = "[foo]"

# stringOfList (stringOfList string_of_int) [[1;2;3];[4;5];[6];[]];;
- : string = "[[1; 2; 3]; [4; 5]; [6]; []]"
```

## Problem #2: Big Numbers

The OCaml type int only contains values upto a certain size. For example,

```# 99999999999999999999999999999999999999999999999 ;;
Error: Integer literal exceeds the range of ...
```
You will now implement functions to manipulate arbitrarily large numbers represented as lists of integers.

### (A) 10 + 5 + 10 = 25 points

Write a curried function

```val clone : ’a -> int -> ’a list
```
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. Once you have implemented the function, you should get the following behavior at the OCaml prompt:
```# clone 3 5;;
- : int list = [3; 3; 3; 3; 3]

# clone "foo" 2;;
- : string list = ["foo"; "foo"]

# clone clone (-3);;
- : (’_a -> int -> ’_a list) list = []
```

Use clone to write a curried function

```val padZero : int list -> int list -> int list * int list
```
which takes two lists `[x1;...;xn]` and `[y1;...;ym]` and adds zeros in front of the shorter list to make the lists equal length. Once you have implemented the function, you should get the following behavior at the OCaml prompt:
```# padZero [9;9] [1;0;0;2];;
- : int list * int list = ([0;0;9;9],[1;0;0;2])

- : int list * int list = ([1;0;0;2],[0;0;9;9])
```

Next, write a function

```val removeZero : int list -> int list
```
that takes a list and removes a prefix of trailing zeros. Once you have implemented the function, you should get the following behavior at the OCaml prompt:
```# removeZero [0;0;0;1;0;0;2];;
- : int list = [1;0;0;2]

# removeZero [9;9];;
- : int list = [9;9]

# removeZero [0;0;0;0];;
- : int list = []
```

### (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`. For example, let `[9;9;9;9;9;9;9;9;9;9]` represent the big-integer `9999999999`. Fill out the implementation for

```val bigAdd : int list -> int list -> int list
```
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`, and `args`. Once you have implemented the function, you should get the following behavior at the OCaml prompt:
```# bigAdd [9;9] [1;0;0;2];;
- : int list = [1;1;0;1]

- : int list = [1;0;9;9;8]
```

### (C) 15 + 20 = 35 points

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

```val mulByDigit : int -> int list -> int list
```
which takes an intger digit and a big integer, and returns the big integer list which is the result of multiplying the big integer with the digit. Once you have implemented the function, you should get the following behavior at the OCaml prompt:
```# mulByDigit 9 [9;9;9;9];;
- :  int list  =  [8;9;9;9;1]
```

Now, using `mulByDigit`, fill in the implementation of

```val bigMul : int list -> int list -> int list
```
Again, you have to fill in implementations for `f`, `base`, and `args` only. Once you are done, you should get the following behavior at the prompt:
```# bigMul [9;9;9;9] [9;9;9;9];;
- : int list = [9;9;9;8;0;0;0;1]

# bigMul [9;9;9;9;9] [9;9;9;9;9];;
- : int list = [9;9;9;9;8;0;0;0;0;1]
```