CSCI 330: Folding in OCaml

Goals

Overview

You 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.

  1. Download the handout file from Autolab
  2. Update each of the functions with your own solutions. As a reminder, you are expected to complete this individually.
  3. Test your program using the OCaml environment installed on the Linux Lab machines
  4. Submit your updated handout file to the “Folding” Autolab assignment.

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 (10 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 -> int

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

Signature

string -> string list -> string

Expected Output

sepConcat ", " ["foo";"bar";"baz"];;
(* string = "foo, bar, baz" *)

sepConcat "---" [];;
(* string = "" *)

sepConcat "," ["hello"];;
(* string = "hello" *)

sepConcat "" ["a";"b";"c"];;
(* string = "abc" *)

stringOfList (5 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 -> string

Expected 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 -> 'a

Expected 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 list

Expected 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 list

Expected 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

Expected 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] *)

Submission

Submit folding.ml to the “Folding” 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!

Grading

90 points total

Attribution

This assignment was adapted from Sorin Lerner’s CSE 130 course at UCSD and slightly modified by Dr. Schwartz, Prof. Killian, and Dr. Zoppetti