Due: Friday, May 11 @ 11:59PM
NO GRACE DAYS MAY BE USED FOR THIS LAB
List operationsYou have been tasked with implementing several functions in OCaml. All of the programs require relatively little coding ranging from 2 to 15 lines. If any function requires more than that, you will need to rethink your solution.
Start this assignment early I cannot emphasize this enough! ML programming is relatively easy (syntax-wise) but it will seem foreign, especially with recursion and list manipulation.
Note: Solutions using imperative features such as references, arrays, or while loops will receive no credit. Do not use any additional libraries, just use standard OCaml as installed in the Linux environment.
sqsum (15 points)Fill in the appropriate values for (1) the folding function, f, and (2) the base case value.
Takes a list of integers [x1;...;xn] as input
Returns an integer representing \[ \sum_{i=1}^{n} x_i^2 \]
Signature:
int list -> intExpected Output
sqsum [];;
(* int = 0 *)
sqsum [1;2;3;4] ;;
(* int = 30 *)
sqsum [-1;-2;-3;-4] ;;
(* int = 30 *)sepConcat (15 points)Fill in the appropriate values for (1) the folding function, f, (2) the base value, base, and (3) the list, l.
This is a curried function which accepts a string separator sep and a list of strings [s1;...;sn]
"" should be returneds1 should be returneds1 sep s2 sep ... sep sn should be returned.Signature
string -> string list -> stringExpected Output
sepConcat ", " ["foo";"bar";"baz"];;
(* string = "foo, bar, baz" *)
sepConcat "---" [];;
(* string = "" *)
sepConcat "," ["hello"];;
(* string = "hello" *)
sepConcat "" ["a";"b";"c"];;
(* string = "abc" *)stringOfList (10 points)Using a single expression/line (with List.map and sepConcat), implement a function which prints a string representation of a list.
This is a curried function which accepts a function, f, which converts the underlying type of the list to a string (e.g. string_of_int for int list) as well as a list, l.
If our list contains the elements [l1;l2;...;ln] you can imagine the functional equivalence being: "[" (f l1) "; " (f l2) "; " ... "; " (f ln) "]"
Signature
('a -> string) -> 'a list -> stringExpected Output
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]; []]" *)pipe (10 points)The function pipe takes a list of functions [f1;...;fn] and returns a function f such that for any x, the application f x returns the result fn(...(f2(f1 x))). Again, your task is to fill in the appropriate values for (1) the folding function f and (2) the base case base.
Signature
('a -> 'a) list -> 'a -> 'aExpected Output
pipe [] 3;;
(* int = 3 *)
pipe [(fun x-> 2*x);(fun x -> x + 3)] 3;;
(* int = 9 *)
pipe [(fun x -> x + 3);(fun x-> 2*x)] 3;;
(* int = 12 *)pipec (10 points)Fill in the skeleton given for pipec, which has the same behavior as pipe above BUT uses function currying. In this version of the function, you will not explicitly take in the second parameter. Instead you will return a function that expects this parameter and uses it when it is received.
Signature
('a -> 'a) list -> ('a -> 'a)Expected Output
pipec [] 3;;
(* int = 3 *)
pipec [(fun x-> 2*x);(fun x -> x + 3)] 3;;
(* int = 9 *)
pipec [(fun x -> x + 3);(fun x-> 2*x)] 3;;
(* int = 12 *)prodLists (10 points)The function prodLists takes two lists of integers [x1;...;xn] and [y1;...;yn (you can assume that they’re the same length) and returns a list of integers with the product of each pair of numbers [x1*y1;...;xn*yn]. Your task is to fill in the appropriate values for (1) the folding function f (2) the base case base and (3) the args being passed to List.fold_left. Hint: Look at using List.combine.
Signature
int list -> int list -> int listExpected Output
prodLists [] [];;
(* int list = [] *)
prodLists [3] [4];;
(* int list = [12] *)
prodLists [10; 20; 30] [5; 5; 5];;
(* int list = [50; 100; 150] *)bigAdd (20 points)As you may have noticed, the OCaml type int only contains values up to a certain size. For example, entering 99999999999999999999 results in the message “Integer literal exceeds the range of representable integers of type int”. This problem involves implementing functions to manipulate large numbers represented as lists of integers.
Several helper functions (clone, padZero, removeZero) have been included in the handout file. Use these in your implementations wherever they are helpful. Each integer will be in the range [0..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. One of the keys here is to realize that your accumulator can carry more than one piece of data. WARNING: this problem is significantly harder than the other problems
Signature
int list -> int list -> int listExpected Output
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] *)
bigMul and mulByDigit (20 points extra credit)Next you will write functions to multiply two big integers.
Signature
mulByDigit has a type signature of: int -> int list -> int listbigMul has a type signature of: int list -> int list -> int listExpected Output
mulByDigit 9 [9;9;9;9];;
(* int list = [8;9;9;9;1] *)
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] *)Submit folding.ml to the Lab 5 assignment through Autolab
NOTE: Autolab will not detect it if you alter the templates. However, the specs for the assignment say that you must use the templates as they appear in the handout. I will be reviewing code and deducting the points for any problems where the template has been altered!
100 points total
This assignment was adapted from Sorin Lerner's CSE 130 course at UCSD and slightly modified by Dr. Schwartz and Prof. Killian