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 spread over two files
that you need to download. The first three files contain several skeleton ML functions, with missing bodies, i.e. expressions, which currently contain the text failwith "to be written". Your task is to replace the text in those files with the the appropriate ML 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 very early as it is somewhat harder than the first two assignments.
Your functions/programs must compile and/or run on a ACS Linux machine (e.g. ieng6.ucsd.edu) as this is where your solutions will be checked. While you may develop your code on any system, ensure that your code runs as expected on an ACS machine prior to submission. You should test your code in the directories from which the zip files (see below) will be created, as this will approximate the environment used for grading the assignment.
Most of the points, will be awarded automatically, by evaluating your functions against a given test suite. test.ml contains a very small suite of tests which gives you a flavor of of these tests. At any stage, by typing at the UNIX shell :
> ocaml test.ml > log
you will get a report on how your code stacks up against the simple tests.
The last line of the file log must contain the word ``Compiled" otherwise you get a zero for the whole assignment.
If for some problem, you cannot get the code to compile, leave it as is with the failwith ... with your partial solution enclosed below as a comment.
The second last line of the log file will contain your overall score, and the other lines will give you a readout for each test. You are encouraged to try to understand the code in test.ml, and subsequently devise your own tests and add them to test.ml, but you will not be graded on this.
Alternately, inside the OCaml shell, type:
> #use "test.ml";;
.
.
.
val it = (...,...) : int * int
and it should return a pair of integers, reflecting your score and the max possible score on the sample tests. If instead an error message appears, your code will receive a zero.
Your solutions to this assignment will be stored in separate files under a directory called solution/, inside which you will place the file: misc.ml. There should be no other files in the directory
After creating and populating the directory as described above, create a zip file called cse130_pa3.zip by going into the directory solution and executing the UNIX shell command:
> zip cse130_pa3.zip ../solution/*.ml
Once you have created the zip file with your solutions, you will use the turnin program to submit this file for grading by going into the directory solution/ and executing the UNIX shell command:
> turnin -c cs130f -p pa3 cse130_pa3.zip
turnin will provide you with a confirmation of the submission process; make sure that the size of the file indicated by turnin matches the size of your zip file. See the ACS Web page on turnin for more information on the operation of the program.
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
Your task is to fill in the appropriate values for
f andbase.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
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
f andbase.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
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"
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]; []]"
The OCaml type int only contains values upto a certain size. For example,
# 99999999999999999999999999999999999999999999999 ;;
Error: Integer literal exceeds the range of representable integers of type int
You will now implement functions to manipulate arbitrarily large numbers represented as lists of integers.
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] [y1;...;ym] and adds zeros in front of the shorter list to make the lists equal. 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 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 = []
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, 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]
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 , 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]