Programming Assignment #1 (60 Points)
Due: Mon, Jan 20, 5:00pm Fri, Jan 17, 5:00pm
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
-
misc.ml, which contains several
skeleton OCaml functions with missing bodies that you will fill in;
-
test.ml which contains some
sample tests for you to start with, which you can extend in order
to test your implementations more fully; and
-
tester.ml, which helps run the tests cases,
so you can check your assignments before submitting.
The file misc.ml contain expressions of the form:
failwith "..."
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.
Assignment Testing and Evaluation
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
% ocaml test.ml > log
at the UNIX shell, you will get a report on how your code stacks up against the
simple tests.
Note: these are only
sample tests, and we will use a larger
test suite when grading your submission.
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";;
...
- : 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.
Submission Instructions
1. Create zip file
Your solutions to this assignment should be stored in separate files in a
directory called solution/, inside which you will place the files:
misc.ml.
There should be no other files in the directory.
After creating and populating the directory as described above, create a
zip file by going into the directory solution/ and executing the UNIX shell
command:
% zip firstname_lastname_cse130_pa1.zip misc.ml
where firstname and lastname have your first and last names respectively.
2. Validate the zip file
Next, you will use the program
validate_pa1 program to determine
whether your zip file’s structure is well-formed. Do this by executing the UNIX
shell command:
% validate_pa1 firstname_lastname_cse130_pa1.zip
The
validate_pa1 program will output OK if your zip file is
well-formed and your solution is compiled. Otherwise, it will output some error
messages.
Before going to step 3, make sure that your zip file passes
validate_pa1 program. Otherwise you get a zero for the whole
assignment. If you have any trouble with this, refer to the instructions in
step 1.
3. Submit the zip file
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 cs130w -p pa1 firstname_lastname_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.
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
Write an OCaml function
val digitsOfInt : int -> int list
such that
digitsOfInt n returns
[] if
n is
not positive
less than zero,
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]
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
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"]
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