ðŸŽ‰ Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io ðŸŽ‰

Published at Jul 13 2018
·
0 comments

Instructions

Test suite

Solution

Create a custom set type.

Sometimes it is necessary to define a custom data structure of some type, like a set. In this exercise you will define your own set. How it works internally doesn't matter, as long as it behaves like a set of unique elements.

For installation and learning resources, refer to the exercism help page.

To work on the exercises, you will need `Opam`

and `Core`

. Consult opam website for instructions on how to install `opam`

for your OS. Once `opam`

is installed open a terminal window and run the following command to install core:

```
opam install core
```

To run the tests you will need `OUnit`

. Install it using `opam`

:

```
opam install ounit
```

A Makefile is provided with a default target to compile your solution and run the tests. At the command line, type:

```
make
```

`utop`

is a command line program which allows you to run Ocaml code interactively. The easiest way to install it is via opam:

```
opam install utop
```

Consult utop for more detail.

The exercism/ocaml repository on GitHub is the home for all of the Ocaml exercises.

If you have feedback about an exercise, or want to help implementing a new one, head over there and create an issue. We'll do our best to help you!

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

```
open OUnit2
module type EXPECTED = sig
type t
val of_list : int list -> t
val is_empty : t -> bool
val is_member : t -> int -> bool
val is_subset : t -> t -> bool
val is_disjoint: t -> t -> bool
val equal : t -> t -> bool
val add : t -> int -> t
val intersect : t -> t -> t
val difference : t -> t -> t
val union : t -> t -> t
end
module CSet : EXPECTED = Custom_set.Make(struct
type t = int
let compare a b = compare (a mod 10) (b mod 10)
end)
let assert_true exp _text_ctxt = assert_equal exp true
let assert_false exp _text_ctxt = assert_equal exp false
let tests = [
"sets with no elements are empty">::
assert_true (CSet.is_empty (CSet.of_list []));
"sets with elements are not empty">::
assert_false (CSet.is_empty (CSet.of_list [1]));
"nothing is contained in the empty set">::
assert_false (CSet.is_member (CSet.of_list []) 1);
"when the element is in the set">::
assert_true (CSet.is_member (CSet.of_list [1;2;3]) 1);
"when the element is not in the set">::
assert_false (CSet.is_member (CSet.of_list [1;3;3]) 4);
"empty set is a subset of an other empty set">::
assert_true (CSet.is_subset (CSet.of_list []) (CSet.of_list []));
"empty set is a subset of a non empty set">::
assert_true (CSet.is_subset (CSet.of_list []) (CSet.of_list [1]));
"non-empty set is a not subset of an empty set">::
assert_false (CSet.is_subset (CSet.of_list [1]) (CSet.of_list []));
"set is a subset of set with exact same elements">::
assert_true (CSet.is_subset (CSet.of_list [1;2;3]) (CSet.of_list [1;2;3]));
"set is a subset of larger set with exact same elements">::
assert_true (CSet.is_subset (CSet.of_list [1;2;3]) (CSet.of_list [4;1;2;3]));
"set is not a subset of set that does not contain its elements">::
assert_false (CSet.is_subset (CSet.of_list [1;2;3]) (CSet.of_list [4;1;3]));
"the empty set is disjoint with itself">::
assert_true (CSet.is_disjoint (CSet.of_list []) (CSet.of_list []));
"the empty set is disjoint with non-empty set">::
assert_true (CSet.is_disjoint (CSet.of_list []) (CSet.of_list [1]));
"non-empty set is disjoint with empty set">::
assert_true (CSet.is_disjoint (CSet.of_list [1]) (CSet.of_list []));
"sets are not disjoint if they share an element">::
assert_false (CSet.is_disjoint (CSet.of_list [1;2]) (CSet.of_list [2;3]));
"sets are disjoint if they do not share an element">::
assert_true (CSet.is_disjoint (CSet.of_list [1;2]) (CSet.of_list [3;4]));
"empty sets are equal">::
assert_true (CSet.equal (CSet.of_list []) (CSet.of_list []));
"empty set is not equal to non-empty set">::
assert_false (CSet.equal (CSet.of_list []) (CSet.of_list [1;2;3]));
"non-empty set is not equal to empty set">::
assert_false (CSet.equal (CSet.of_list [1;2;3]) (CSet.of_list []));
"sets with the same elements are equal">::
assert_true (CSet.equal (CSet.of_list [1;2]) (CSet.of_list [2;1]));
"sets with different elements are not equal">::
assert_false (CSet.equal (CSet.of_list [1;2;3]) (CSet.of_list [1;2;4]));
"add to empty set">::
assert_true (CSet.equal (CSet.of_list [3]) (CSet.add (CSet.of_list []) 3));
"add to non-empty set">::
assert_true (CSet.equal (CSet.of_list [1;2;3;4]) (CSet.add (CSet.of_list [1;2;4]) 3));
"adding existing element does not change set">::
assert_true (CSet.equal (CSet.of_list [1;2;3]) (CSet.add (CSet.of_list [1;2;3]) 3));
"intersection of two empty sets is empty set">::
assert_true (CSet.equal (CSet.of_list []) (CSet.intersect (CSet.of_list []) (CSet.of_list [])));
"intersection of empty set with non-empty set is an empty set">::
assert_true (CSet.equal (CSet.of_list []) (CSet.intersect (CSet.of_list []) (CSet.of_list [3;2;5])));
"intersection of non-empty set with empty set is an empty set">::
assert_true (CSet.equal (CSet.of_list []) (CSet.intersect (CSet.of_list [1;2;3;4]) (CSet.of_list [])));
"intersection of sets with no shared elements is empty set">::
assert_true (CSet.equal (CSet.of_list []) (CSet.intersect (CSet.of_list [1;2;3]) (CSet.of_list [4;5;6])));
"intersection of set with shared elements is set of shared elements">::
assert_true (CSet.equal (CSet.of_list [2;3]) (CSet.intersect (CSet.of_list [1;2;3;4]) (CSet.of_list [3;2;5])));
"difference of two empty sets is an empty set">::
assert_true (CSet.equal (CSet.of_list []) (CSet.difference (CSet.of_list []) (CSet.of_list [])));
"difference of empty set and non-empty set is empty set">::
assert_true (CSet.equal (CSet.of_list []) (CSet.difference (CSet.of_list []) (CSet.of_list [3;2;5])));
"difference of non-empty set and empty set is the non-empty set">::
assert_true (CSet.equal (CSet.of_list [1;2;3;4]) (CSet.difference (CSet.of_list [1;2;3;4]) (CSet.of_list [])));
"difference of two non-empty sets is the sets of elements only in the first set">::
assert_true (CSet.equal (CSet.of_list [1;3]) (CSet.difference (CSet.of_list [3;2;1]) (CSet.of_list [2;4])));
"union of two empty sets is an empty set">::
assert_true (CSet.equal (CSet.of_list []) (CSet.union (CSet.of_list []) (CSet.of_list [])));
"union of empty set and non-empty set is non-empty set">::
assert_true (CSet.equal (CSet.of_list [2]) (CSet.union (CSet.of_list []) (CSet.of_list [2])));
"union of non-empty set and empty set is the non-empty set">::
assert_true (CSet.equal (CSet.of_list [1;3]) (CSet.union (CSet.of_list [1;3]) (CSet.of_list [])));
"union of two non-empty sets contains all unique elements">::
assert_true (CSet.equal (CSet.of_list [1;2;3]) (CSet.union (CSet.of_list [1;3]) (CSet.of_list [2;3])));
]
let () =
run_test_tt_main ("custom_set tests" >::: tests)
```

```
(* custom set *)
module type ELT = sig
type t
val compare : t -> t -> int
val equal : t -> t -> bool
val to_string : t -> string
end
(* We will implement sets as randomized binary search trees *)
module Make (M : ELT) = struct
type elt = M.t
type t =
| Empty
| Node of t * elt * t
let empty = Empty
let singleton elt = Node (empty, elt, empty)
let rec remove_max = function
| Empty -> assert false
| Node (l, x, Empty) -> x, l
| Node (l, x, r) ->
let max, remaining = remove_max r in
max, Node(l, x, remaining)
let rec remove_min = function
| Empty -> assert false
| Node (Empty, x, r) -> x, r
| Node (l, x, r) ->
let minx, removed = remove_min l in
minx, Node(removed, x, r)
let rec remove tree elt =
begin match tree with
| Empty -> Empty
| Node (Empty, x, Empty) when M.equal x elt -> Empty
| Node (Empty, _, Empty) -> tree
| Node (l, x, r) when M.compare elt x < 0 -> Node (remove l elt, x, r)
| Node (l, x, r) when M.compare elt x > 0 -> Node (l, x, remove r elt)
(* At this point we have: M.equal x elt *)
| Node (Empty, _, r) -> r
| Node (l, _, Empty) -> l
| Node (l, _, r) ->
let mx, lx = remove_max l in
Node (lx, mx, r)
end
let rec add_ordered tree elt =
begin match tree with
| Empty -> singleton elt
| Node (l, x, r) ->
if M.equal elt x then
tree
else
if M.compare elt x < 0 then
Node (add_ordered l elt, x, r)
else
Node (l, x, add_ordered r elt)
end
let randomized_add tree elt =
begin match tree with
| Empty -> singleton elt
(* checking for Empty branches here, simplifies the code below, allowing us to
assume that relevant branches are not empty and
we can call remove_min remove_max on them
*)
| Node (Empty, x, r) when M.compare elt x < 0 -> Node (singleton elt, x, r)
| Node (l, x, Empty) when M.compare elt x > 0 -> Node (l, x, singleton elt)
| Node (_, x, _) when M.equal elt x -> tree
| Node (l, x, r) ->
(* the randomized bit *)
let flip = Random.bool () in
if flip then
add_ordered tree elt
else
if M.compare elt x < 0 then
let lmax, lrest = remove_max l in
if M.compare elt lmax < 0 then
Node (add_ordered lrest elt, lmax, add_ordered r x)
else
if M.equal elt lmax then
Node(lrest, elt, add_ordered r x)
else
Node(l, elt, add_ordered r x)
else
let rmin, rrest = remove_min r in
if M.compare elt rmin > 0 then
Node (add_ordered l x, rmin, add_ordered rrest elt)
else
if M.equal elt rmin then
Node (add_ordered l x, elt, rrest)
else
Node (add_ordered l x, elt, r)
end
let add = randomized_add
let rec fold ~f ~acc tree =
begin match tree with
| Empty -> acc
| Node (l, x, r) ->
let acc = fold ~f ~acc l in
let acc = f acc x in
fold ~f ~acc r
end
let to_list tree = fold ~f:(fun acc x -> x :: acc) ~acc:[] tree |> List.rev
let of_list elts = List.fold_left add empty elts
let to_string tree = to_list tree |> List.map M.to_string |> String.concat " "
let to_string tree = "{" ^ to_string tree ^ "}"
let rec member tree elt =
begin match tree with
| Empty -> false
| Node (_, x, _) when M.equal elt x -> true
| Node (l, x, _) when M.compare elt x < 0 -> member l elt
| Node (_, _, r) -> member r elt
end
let rec compare t1 t2 =
begin match t1, t2 with
| Empty, Empty -> 0
| _, Empty -> 1
| Empty, _ -> -1
| _ ->
let min1, t1 = remove_min t1 in
let min2, t2 = remove_min t2 in
let c = M.compare min1 min2 in
if c <> 0 then
c
else
compare t1 t2
end
let equal t1 t2 = compare t1 t2 = 0
let difference t1 t2 = fold ~f:remove ~acc:t1 t2
let intersect t1 t2 = fold
~f:(fun acc elt -> if member t2 elt then add acc elt else acc)
~acc:empty
t1
let union t1 t2 = fold ~f:add ~acc:t1 t2
end
```

A huge amount can be learned from reading other peopleâ€™s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

- What compromises have been made?
- Are there new concepts here that you could read more about to improve your understanding?

Level up your programming skills with 3,450 exercises across 52 languages, and insightful discussion with our volunteer team of welcoming mentors.
Exercism is
**100% free forever**.

## Community comments