Important notes about grading:

  1. Compiler errors: Programs that cannot be compiled will receive an automatic zero. If you are having trouble getting your assignment to compile, please visit recitation or office hours.
  2. Late assignments: Please carefully review the course website's policy on late assignments, as all assignments handed in after the deadline will be considered late. Submitting an incorrect version before the deadline and realizing that you have done so after the deadline will be counted as a late submission.

Compile and run your code:

After downloading and unzipping the file for assignment1, in your command-line window, cd into the directory which contains src. You should write your code in src/assignment1.ml.

Use ocamlc -o test src/assignment1.ml to compile the code. Then, use ./test to excute it.

Submission:

Please submit to Sakai with assignment1.ml only.

Problem 1

Write a function

range : int -> int -> int list

such that range num1 num2 returns an ordered list of all integers from num1 to num2 inclusive. For example, range 2 5 = [2;3;4;5]. Return [] if num2 < num1.

In [ ]:
let rec range num1 num2 =
  (* YOUR CODE HERE *)
In [ ]:
assert (range 2 5 = [2;3;4;5])

Problem 2

Write a function

flatten : 'a list list -> 'a list

that flattens a list. For example, flatten [[1;2];[4;3]] = [1;2;4;3].

In [ ]:
let rec flatten l =
  (* YOUR CODE HERE *)
In [ ]:
assert (flatten ([[1;2];[4;3]]) = [1;2;4;3])

Problem 3

Write a function

remove_stutter : 'a list -> 'a list

that removes stuttering from the original list. For example, remove_stutter [1;2;2;3;1;1;1;4;4;2;2]= [1;2;3;1;4;2].

In [ ]:
let remove_stutter l =
  (* YOUR CODE HERE *)
In [ ]:
assert (remove_stutter [1;2;2;3;1;1;1;4;4;2;2] = [1; 2; 3; 1; 4; 2])

Problem 4 (3 questions)

Set Implementation using Lists

For this part of the project, you will implement sets. In practice, sets are implemented using data structures like balanced binary trees or hash tables. However, your implementation must represent sets using lists. While lists don’t lend themselves to the most efficient possible implementation, they are much easier to work with.

For this project, we assume that sets are unordered, homogeneous collections of objects without duplicates. The homogeneity condition ensures that sets can be represented by OCaml lists, which are homogeneous. The only further assumptions we make about your implementation are that the empty list represents the empty set, and that it obeys the standard laws of set theory. For example, if we insert an element x into a set a, then ask whether x is an element of a, your implementation should answer affirmatively.

Finally, note the difference between a collection and its implementation. Although sets are unordered and contain no duplicates, your implementation using lists will obviously store elements in a certain order and may even contain duplicates. However, there should be no observable difference between an implementation that maintains uniqueness of elements and one that does not; or an implementation that maintains elements in sorted order and one that does not.

If you do not feel so comfortable with sets see the Set Wikipedia Page) and/or this Set Operations Calculator.

We provide some example code.

elem : 'a -> 'a list -> bool

elem x a returns true iff x is an element of the set a. For example, elem 5 [2;3;5;7;9] = true.

In [ ]:
let rec elem x a =
  match a with
  | [] -> false
  | h::t -> if h = x then true else elem x t

subset: 'a list -> 'a list -> bool

subset a b returns true iff a is a subset of b. For example, subset [5] [2;3;5;7;9] = true.

In [ ]:
let rec subset a b =
  match a with
  | [] -> true
  | h::t -> if elem h b then subset t b else false

eq: 'a list -> 'a list -> bool

eq a b returns true iff a and b are equal as sets. For example, eq [5;3;2;9;7] [2;3;5;7;9] = true.

In [ ]:
let rec eq a b =
  (subset a b) && (subset b a)

You need to implement the following three functions:

remove: 'a -> 'a list -> 'a list

remove x a removes x from the set a. For example, eq (remove 5 [2;3;5;7;9]) [2;3;9;7] = true.

In [ ]:
let rec remove x a =
  (* YOUR CODE HERE *)
In [ ]:
assert (eq (remove 5 []) []);
assert (eq (remove 5 [2;3;5;7;9]) [2;3;9;7]);
assert (eq (remove 4 [2;3;5;7;9]) [2;3;5;9;7]);

union: 'a list -> 'a list -> 'a list

union a b returns the union of the sets a and b. For example, eq (union [5;2] [3;7;9]) [2;3;5;7;9] = true.

In [ ]:
let rec union a b =
  (* YOUR CODE HERE *)
In [ ]:
assert (eq (union [2;3;5] []) [2;3;5]);
assert (eq (union [5;2] [3;7;9]) [2;3;5;9;7]);
assert (eq (union [2;3;9] [2;7;9]) [2;3;9;7]);

diff: 'a list -> 'a list -> 'a list

diff a b returns the difference of sets a and b in a. For example, eq (diff [1;3;2] [2;3]) [1] = true.

In [ ]:
let rec diff a b =
  (* YOUR CODE HERE *)
In [ ]:
assert (eq (diff [1;3;2] [2;3]) [1]);
assert (eq (diff ['a';'b';'c';'d'] ['a';'e';'i';'o';'u']) ['b';'c';'d']);
assert (eq (diff ["hello";"ocaml"] ["hi";"python"]) ["hello";"ocaml"]);