The objective of this assignment is for you to gain some hands-on experience with OCaml. All the problems require relatively little code ranging from 2 to 15 lines. If any function requires more than that, you can be sure that you need to rethink your solution.
The assignment is in the single zip file
that you need to download. After downloading to an appropriate directory, unzip it thus:
> unzip pa1.zip
and out come tumbling several files including
tester.ml, which is a dummy tester that you will use to check your assignments before submitting,test.ml, which contains some sample tests for you to start with, placeholders where you will fill in new tests, andmisc.ml, which contains several skeleton Ocaml functions with missing bodies that you will fill in.All but the first file contain expressions of the form:
failwith "TBD: ..."
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.
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 the log file contains a line WARNING: Your tests are not valid then there is a problem with one or more tests and you may not get the points for them
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 tester.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 files: misc.ml and test.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_pa1.zip by going into the directory solution and executing the UNIX shell command:
> zip cse130_pa1.zip *.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 pa1 cse130_pa1.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.
For each problem below, in addition to writing code, you will be writing tests by filling in the templates as described below. Note that
When writing tests, do not use the same values as in the sampleTests or you will get a zero for that problem.
We will run everyone’s code against everyone’s tests. The tests will then be ranked by the maximum number of failures they induce. If one of your tests is among the top–10 failure-inducing tests, you get 25 points (in addition to the points for writing valid tests.)
Write an OCaml function
val sumList : int list -> int
that such that sumList xs returns the sum of the integer elements of xs. Once you have implemented the function, you should get the following behavior at the OCaml prompt:
# sumList [1; 2; 3; 4];;
- : int = 10
# sumList [1; -2; 3; 5];;
- : int = 7
# sumList [1; 3; 5; 7; 9; 11];;
- : int = 36
In the file test.ml write down five (5) tests for the sumList by filling in the input and output expressions appropriately following the example shown above for sampleTests. For example, to describe the test case where the input is [1;2;3;4] and the output is 10 (the test labeled "sample: sumList 1"), - replace failwith "TBD:input" with the expression [1;2;3;4] and - replace failwith "TBD:output" with the expression 10.
Write an OCaml function
val digitsOfInt : int -> int list
such that digitsOfInt n returns [] if n is not positive, and returns the list of digits of n in the order in which they appear in n. Once you have implemented the function, you should get the following behavior at the OCaml prompt:
# digitsOfInt 3124;;
- : int list = [3; 1; 2; 4]
# digitsOfInt 352663;;
- : int list = [3; 5; 2; 6; 6; 3]
In the file test.ml write down five (5) tests for the digitsOfInt by filling in the input and output expressions appropriately following the example shown above for sampleTests. For example, to describe the test case where the input is 3124 and the output is [3;1;2;4] (the test labeled "sample: digitsOfInt 1"), - replace failwith "TBD:input" with the expression 3124 and - replace failwith "TBD:output" with the expression [3;1;2;4].
NOTE: Do not use the same values as in the sampleTests or you will receive no points.
Consider the process of taking a number, adding its digits, then adding the digits of the number derived from it, etc., until the remaining number has only one digit. The number of additions required to obtain a single digit from a number n is called the additive persistence of n, and the digit obtained is called the digital root of n.
For example, the sequence obtained from the starting number 9876 is 9876, 30, 3, so 9876 has an additive persistence of 2 and a digital root of 3.
Write two OCaml functions
val additivePersistence : int -> int
val digitalRoot : int -> int
that take positive integer arguments n and return respectively the additive persistence and the digital root of n. Once you have implemented the functions, you should get the following behavior at the OCaml prompt:
# additivePersistence 9876;;
- : int = 2
# digitalRoot 9876;;
- : int = 3
In the file test.ml write down five (5) tests each for the additivePersistence and digitalRoot functions by filling in the input and output expressions appropriately following the example shown above for sampleTests as described previously.
Without using any built-in OCaml functions, write an OCaml function:
val listReverse : 'a list -> 'a list
such that listReverse xs returns the list of elements of xs in the reversed order (in which the appear in xs.) Once you have implemented the function, you should get the following behavior at the OCaml prompt:
# listReverse [1; 2; 3; 4];;
- : int list = [4; 3; 2; 1]
# listReverse ["a"; "b"; "c"; "d"];;
- : string list = ["d"; "c"; "b"; "a"]
In the file test.ml write down five (5) tests each for the listReverse function by filling in the input and output expressions appropriately following the example shown above for sampleTests as described previously.
A palindrome is a word that reads the same from left-to-right and right-to-left. Write an OCaml function
val palindrome : string -> bool
such that palindrome w returns true if the string is a palindrome and false otherwise. You may use the given helper function explode. Once you have implemented the function, you should get the following behavior at the OCaml prompt:
# palindrome "malayalam";;
- : bool = true
# palindrome "myxomatosis";;
- : bool = false
In the file test.ml write down five (5) tests each for the palindrome function by filling in the input and output expressions appropriately following the example shown above for sampleTests as described previously.