Project 3 - OCaml Warmup

Introduction

This project will give you practice writing code in OCaml.

Getting Started

Along with files used to make direct submissions to the submit server (submit.jar, .submit, submit.rb), you will find the following project files:

• Three OCaml programs - part1.ml, part2.ml, and part3.ml
• Utility code - testUtils.ml
• Public test
  • public_1.ml
  • public_2.ml
  • public_3.ml
  • public_4.ml
  • public_5.ml
  • public_6.ml
  • public_7.ml
  • public_8.ml
  • public_9.rb
• Expected outputs for public tests
  • public_1.out
  • public_1.out
  • public_3.out
  • public_4.out
  • public_5.out
  • public_6.out
  • public_7.out
  • public_8.out
  • public_9.out
• Test Script - goTest.rb
• New Test Cases - myTest.ml

Part 1: Simple OCaml functions

• 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 first 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

• As you know, unsigned integers can be represented in binary notation. We can represent a binary number by a list of booleans, 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]
  • 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 ot 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 an arithmetic 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). Remember that the most significant "digit" is the sign bit. 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.
  • Write a function add : bool list -> bool list -> bool list to add two lists of booleans. Use only boolean and list operations. Your adder only needs to work on positive integers.

• In Squaresville, streets are numbered 1..M and the perpendicular avenues are numbered 1..N. Your task is to write a function
  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. 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.

Part 3: Frequency Counts

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:

1. We will compile your file with ocamlc part3.ml, and then run the resulting a.out file to execute your program.
2. 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.
3. Lower and upper case letters are equivalent and should be printed as upper case characters.
4. 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 ' '.
5. 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.
6. 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.

7. The frequency counts should be printed in decreasing order of occurrence.
8. 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.
9. Do NOT use arrays in your solution. (That makes the problem way too simple! The goal is to get you familiar with functional programming.)

Example

% ocamlc part3.ml
% ./a.out
foo: bar
baz qux
^D
FO:spaceBARZQUX
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.

Clarifications

• For parts 1 & 2, you should implement everything on your own. So, this means no using the OCaml List module.
• For part 3, you can use List, but should not use the String module to process the input.
• For part 2, none of the binary operations should use other binary operations that you've already made.
• For part 3, make sure you take the input from standard input (stdin). 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.)

Submission

• Submit your fa.rb file directly to the submit server by clicking on the submit link in the column "web submission".

  

  Next, use the submit dialog to submit your fa.rb file directly.

  

  Select your file using the "Browse" button, then press the "Submit project!" button. You do not need to put it in a Jar or Zip file. Some students have mentioned problems with using Internet Explorer, because submissions being extracted in directories (e.g., "C:\My Documents\330\part1.ml") where the submit server could not find them. The problems went away when switching to the Mozilla Firefox browser.

• Submit directly by executing a Java program on a computer with Java and network access. Use the submit.jar file from the archive p3.zip, 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 2

Hints and Tips