Due 11:59pm Saturday, Apr 5th, 2008
This project will give you practice writing code in OCaml.
Do not use any imperative style in your programs .
(i.e., no loops or assignments changing the value of symbols)
- Apr 2 1-day extension for Project 3, deadline is now 11:59pm Saturday
, April 5th, 2008.
- Apr 1 Added examples
of how I/O may be used for part 3.
- Mar 28 Public/release tests have been added to project 3.
Project description has been modified, mostly to simplify the
portion of the project on using lists of booleans to represent integers.
- For Unix: Download the archive file p3.tar
and extract its contents using the command: tar xf p3.tar.
- For Windows: Download the zip file p3.zip
and extract its contents by double-clicking on the icon.
Along with files used to make direct submissions to the
submit server (submit.jar, .submit, submit.rb), you will
find the following project files:
- Your OCaml programs
- Public tests
- Expected output for public test
- Utility code
- Directions on how to run public tests
Part 1: Simple OCaml functions
Put your solutions to this part in part1.ml
- Write a function prod l : int list -> int that returns
the product of the elements of l. The function prod should
return 1 if the list is empty.
- Write a function index l e : 'a list -> 'a -> int which takes a
list and a single element and returns the position of the last occurrence of
that element in the list (indexed by zero). You should return -1 if the element
is not in the list.
- Write a function unzip l : ('a*'b) list -> ('a list)*('b
list) that given a list of pairs, returns a pair of lists with
the elements in the same order. For example, unzip [(1, 2); (3,
4)] = ([1; 3], [2;4]).
- Write a function app_int f m n : (int->'a)->int->int->'a
list that returns the list [f m; f (m+1); ...; f n]. It
should return the empty list if n<m
Part 2: More interesting OCaml functions
Put your solutions to this part in part2.ml
- As you know, unsigned integers can be represented in binary
notation. We can represent a binary number by a list of booleans
(where true = 1, false = 0), with the least significant "digit" first.
For example, we might
represent decimal 12 (binary 1100) as [false; false; true; true]
or decimal 6 (binary 110) as [false; true; true].
Zero is represented by [false].
- Write a function itob : int -> bool list to convert a positive
OCaml integer to a list of booleans, following the encoding above.
(You may assume the argument to itob is positive.)
- Write a function btoi : bool list -> int to convert from
a list of booleans to an OCaml integer.
- Write a function shift : bool list -> bool -> bool list
that performs a logic shift on the boolean value.
This function should take a list and a boolean value indicating if the
shift is a left shift or right shift (use true for right shifts
and false for left shifts).
Assume that the space used to store the given
list is the full space available, so the input and output should be lists
of the same length.
Shift should work as for a normal
binary number no matter how the binary number is represented.
That is, in the right shift, the least "significant" bit in the
binary will be moved out (lost) and in the left shift, the most
"significant" bit will be moved out (lost). For each shift, a zero
is always shifted in instead.
- Write a function add : bool list -> bool list -> bool
list to add two lists of booleans. Use only boolean and list operations.
Note: none of the binary operations should use other binary operations that you've already made.
- In Squaresville, streets are numbered 1..M and the
perpendicular avenues are numbered 1..N. Your task is to write
paths f m n : (int->int->bool)->int->int->int
that computes the number of ways to get from mth street at
nth avenue to 1st street at 1st avenue without going
backwards, meaning you always move to a lower numbered street or
avenue. During the searching of paths, print out each obtained path
from mth street at nth avenue to 1st street at
1st avenue as a string in the format
where each tuple represents an intersection on the path during
the searching. Each string for a path takes one line in the outputs.
Note that there are m + n - 1 tuples in each output path.
Unfortunately, some of the intersections are blocked. The
first argument to paths, f, is a function such that
f i j returns true if ith street at
jth avenue is blocked, and false otherwise.
Here are some example cases you might want to try.
- m = 5, n = 7, f = fun i j -> false
- m = 5, n = 7, f = fun i j -> (i=3) && (j=4)
- m = 10, n = 10, f = fun i j -> (i mod 2 = 0) && (j mod 2 = 0)
Note that paths(fun i j -> false) 1 1 should return 1. Though you
cannot move through a blocked intersection , you can start at one, so
paths(fun i j -> true) 1 1 should also return 1.
The order for printing the
paths does not matter. You only need to find out the right number of
paths and print out each path correctly.
Part 3: Frequency Counts
Put your solution to this part in part3.ml
For this part, write a program that computes frequency counts for all
characters in an input file. The input to your program is a text
file. As output, your program first prints a line that lists the
characters that appeared in the file, in the order in which the
characters are first seen. Then after that line is a list of the
number of times each character appears, ordered by number of
occurrences of each character. In particular:
- We will compile your file with ocamlc part3.ml, and then
run the resulting a.out file to execute your program.
- Your program should read its input file from standard input and
write its output to standard output. The input file will contain 0 or
more lines of text. (There are lots of ways that you can do this,
some will make your life easier than others... check out the OCaml modules.
The ^D (or control D) shown in the input is how that input stream is ended.)
- Lower and upper case letters are equivalent and should be printed
as upper case characters.
- All whitespace characters (tab, space, newline) count as the
single "space" character. All other characters count as separate
characters. The space should be sorted in the same position as Ocaml
- Your program should first print one line containing each unique
character appearing in the file, in the order that each character is
first seen. No other characters appear on this line. The "space"
character should be printed as the five letters space.
After printing the line containing all the characters, for each character in that
line print a line with the following format:
Character[x] appears y times.
with x and y replaced by the appropriate values. y is an integer
with no leading 0. For the "space" character, x should be space.
The frequency counts should be printed in decreasing order of occurrence.
- If two frequency counts are the same, print them in lexicographic
(i.e., alphabetical) order. Space comes before any letter in the
alphabet. Special characters should be printed in their ASCII order.
Do NOT use arrays or hash table in your solution.
(That makes the problem way
too simple! The goal is to get you familiar with functional
(the ^D means type control-D)
% ocamlc part3.ml
Character[space] appears 4 times.
Character[A] appears 2 times.
Character[B] appears 2 times.
Character[O] appears 2 times.
Character[:] appears 1 times.
Character[F] appears 1 times.
Character[Q] appears 1 times.
Character[R] appears 1 times.
Character[U] appears 1 times.
Character[X] appears 1 times.
Character[Z] appears 1 times.
You can submit your project in two ways:
Put your program files part1.ml, part2.ml, and part3.ml files
in a zip file and submit it to the
by clicking on the submit link in the column "web submission".
Next, use the submit dialog to submit your zip file.
Select your file using the "Browse" button,
then press the "Submit project!" button.
Submit directly by executing a Java program on a computer
with Java and network access. Use the submit.jar file
from the archive p3.tar,
To submit, go to the directory containing your project, then either
execute submit.rb or type the following command directly:
java -jar submit.jar
You will be asked to enter your class account and password, then
all files in the directory (and its subdirectories) will be
put in a jar file and submitted to the submit server.
If your submission is successful you will see the message:
Successful submission # received for project 3
Hints and Tips
Be sure you have read and understand the project grading policies in
the course syllabus. Do this well in advance of the project due date.
The Campus Senate has adopted a policy asking students to include the
following statement on each assignment in every course: "I pledge on
my honor that I have not given or received any unauthorized assistance
on this assignment." Consequently your program is requested to
contain this pledge in a comment near the top.
Please carefully read the academic honesty section of the
course syllabus. Any evidence of impermissible cooperation on
projects, use of disallowed materials or resources, or unauthorized
use of computer accounts, will be submitted to the Student
Honor Council, which could result in an XF for the course, or
suspension or expulsion from the University. Be sure you understand
what you are and what you are not permitted to do in regards to
academic integrity when it comes to project assignments. These
policies apply to all students, and the Student Honor Council does not
consider lack of knowledge of the policies to be a defense for
violating them. Full information is found in the course
syllabus---please review it at this time.