## Programming Assignment #3 (160 Points)## Due: Fri, Feb 07, 5:00pm
The overall objective of this assignment is to expose you to fold,
The assignment is in the single zip file that you need to download. After downloading to an appropriate directory, unzip it thus:> unzip pa3.zipand 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 failwith "..."Your task is to replace the text in those files with the the appropriate OCaml code for each of those expressions.
## Assignment Testing and EvaluationSame as for Assignment #1. ## Submission InstructionsSame 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
val sqsum : int list -> intsuch that `sqsum [x1;...;xn]` returns the integer ```
x1^2 + ... +
xn^2
```
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: # 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 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 pointsFill in the skeleton given for sepConcat, which uses`List.fold_left` to get an OCaml function
val sepConcat : string -> string list -> stringIntuitively, 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 pointsImplement the curried OCaml function val stringOfList : (’a -> string) -> ’a list -> stringsuch 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 # 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 NumbersThe 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 pointsWrite a curried function val clone : ’a -> int -> ’a listsuch 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 listwhich 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]) # padZero [1;0;0;2] [9;9];; - : int list * int list = ([1;0;0;2],[0;0;9;9])
Next, write a function val removeZero : int list -> int listthat 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 val bigAdd : int list -> int list -> int listso 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] # bigAdd [9;9;9;9] [9;9;9];; - : int list = [1;0;9;9;8] ## (C) 15 + 20 = 35 pointsNext you will write functions to multiply two big integers. First write a function val mulByDigit : int -> int list -> int listwhich 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 val bigMul : int list -> int list -> int listAgain, 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] |