Project 3

Updates

• Oct 17. Another typo fix to part 3---the colon in the example should have come later.
• Oct 16. Fix for part 3 example--the colon character comes before A. (The space should be sorted in the same position as OCaml ' '.)
• Oct 16. Two clarifications to part 2:
  • paths (fun i j -> false) 1 1 should return 1.
  • Let's assume that you cannot move through a blocked intersection, but you can begin or end at one that's blocked. So then paths (fun i j -> true) 1 1 should also return 1.
• Oct 16. Fixed type of paths function.
• Oct 14. Fixed typo in part 3. There are 4 space characters in the example.

Introduction

This project will give you practice writing code in OCaml.

What to Submit

You should submit three files, part1.ml, part2.ml, and part3.ml.

You can find a p3 directory here that contains a .submit file:

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 max l : int list -> int that returns the largest integer in l. You may assume that l is not empty.

• 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]
  • Write a function itob : int -> bool list to convert a positive OCaml integer to a list of boolaens, 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 double : bool list -> bool list that doubles the value represented by a boolean list. Use only boolean and list operations.
  • Write a function add : bool list -> bool list -> bool list to add two lists of booleans. Use only boolean and list operations.

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

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

Academic Integrity

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.