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 library documentation, follow Useful OCaml resources.
A Makefile
is provided with a default target to compile your solution and run the tests. At the command line, type:
make
It's possible to submit an incomplete solution so you can see how others have completed the exercise.
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 or submit a PR. We welcome new contributors!
(* custom-set - 1.3.0 *)
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 ae exp got _test_ctxt = assert_equal exp got
let aec exp got _test_ctxt = assert_equal true (CSet.equal (CSet.of_list exp) got)
let tests = [
(* Returns true if the set contains no elements *)
"sets with no elements are empty" >::
ae true (CSet.is_empty (CSet.of_list []));
"sets with elements are not empty" >::
ae false (CSet.is_empty (CSet.of_list [1]));
(* Sets can report if they contain an element *)
"nothing is contained in an empty set" >::
ae false (CSet.is_member (CSet.of_list []) 1);
"when the element is in the set" >::
ae true (CSet.is_member (CSet.of_list [1; 2; 3]) 1);
"when the element is not in the set" >::
ae false (CSet.is_member (CSet.of_list [1; 2; 3]) 4);
(* A set is a subset if all of its elements are contained in the other set *)
"empty set is a subset of another empty set" >::
ae true (CSet.is_subset (CSet.of_list []) (CSet.of_list []));
"empty set is a subset of non-empty set" >::
ae true (CSet.is_subset (CSet.of_list []) (CSet.of_list [1]));
"non-empty set is not a subset of empty set" >::
ae false (CSet.is_subset (CSet.of_list [1]) (CSet.of_list []));
"set is a subset of set with exact same elements" >::
ae true (CSet.is_subset (CSet.of_list [1; 2; 3]) (CSet.of_list [1; 2; 3]));
"set is a subset of larger set with same elements" >::
ae 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" >::
ae false (CSet.is_subset (CSet.of_list [1; 2; 3]) (CSet.of_list [4; 1; 3]));
(* Sets are disjoint if they share no elements *)
"the empty set is disjoint with itself" >::
ae true (CSet.is_disjoint (CSet.of_list []) (CSet.of_list []));
"empty set is disjoint with non-empty set" >::
ae true (CSet.is_disjoint (CSet.of_list []) (CSet.of_list [1]));
"non-empty set is disjoint with empty set" >::
ae true (CSet.is_disjoint (CSet.of_list [1]) (CSet.of_list []));
"sets are not disjoint if they share an element" >::
ae false (CSet.is_disjoint (CSet.of_list [1; 2]) (CSet.of_list [2; 3]));
"sets are disjoint if they share no elements" >::
ae true (CSet.is_disjoint (CSet.of_list [1; 2]) (CSet.of_list [3; 4]));
(* Sets with the same elements are equal *)
"empty sets are equal" >::
ae true (CSet.equal (CSet.of_list []) (CSet.of_list []));
"empty set is not equal to non-empty set" >::
ae false (CSet.equal (CSet.of_list []) (CSet.of_list [1; 2; 3]));
"non-empty set is not equal to empty set" >::
ae false (CSet.equal (CSet.of_list [1; 2; 3]) (CSet.of_list []));
"sets with the same elements are equal" >::
ae true (CSet.equal (CSet.of_list [1; 2]) (CSet.of_list [2; 1]));
"sets with different elements are not equal" >::
ae false (CSet.equal (CSet.of_list [1; 2; 3]) (CSet.of_list [1; 2; 4]));
"set is not equal to larger set with same elements" >::
ae false (CSet.equal (CSet.of_list [1; 2; 3]) (CSet.of_list [1; 2; 3; 4]));
(* Unique elements can be added to a set *)
"add to empty set" >::
aec [3] (CSet.add (CSet.of_list []) 3);
"add to non-empty set" >::
aec [1; 2; 3; 4] (CSet.add (CSet.of_list [1; 2; 4]) 3);
"adding an existing element does not change the set" >::
aec [1; 2; 3] (CSet.add (CSet.of_list [1; 2; 3]) 3);
(* Intersection returns a set of all shared elements *)
"intersection of two empty sets is an empty set" >::
aec [] (CSet.intersect (CSet.of_list []) (CSet.of_list []));
"intersection of an empty set and non-empty set is an empty set" >::
aec [] (CSet.intersect (CSet.of_list []) (CSet.of_list [3; 2; 5]));
"intersection of a non-empty set and an empty set is an empty set" >::
aec [] (CSet.intersect (CSet.of_list [1; 2; 3; 4]) (CSet.of_list []));
"intersection of two sets with no shared elements is an empty set" >::
aec [] (CSet.intersect (CSet.of_list [1; 2; 3]) (CSet.of_list [4; 5; 6]));
"intersection of two sets with shared elements is a set of the shared elements" >::
aec [2; 3] (CSet.intersect (CSet.of_list [1; 2; 3; 4]) (CSet.of_list [3; 2; 5]));
(* Difference (or Complement) of a set is a set of all elements that are only in the first set *)
"difference of two empty sets is an empty set" >::
aec [] (CSet.difference (CSet.of_list []) (CSet.of_list []));
"difference of empty set and non-empty set is an empty set" >::
aec [] (CSet.difference (CSet.of_list []) (CSet.of_list [3; 2; 5]));
"difference of a non-empty set and an empty set is the non-empty set" >::
aec [1; 2; 3; 4] (CSet.difference (CSet.of_list [1; 2; 3; 4]) (CSet.of_list []));
"difference of two non-empty sets is a set of elements that are only in the first set" >::
aec [1; 3] (CSet.difference (CSet.of_list [3; 2; 1]) (CSet.of_list [2; 4]));
(* Union returns a set of all elements in either set *)
"union of empty sets is an empty set" >::
aec [] (CSet.union (CSet.of_list []) (CSet.of_list []));
"union of an empty set and non-empty set is the non-empty set" >::
aec [2] (CSet.union (CSet.of_list []) (CSet.of_list [2]));
"union of a non-empty set and empty set is the non-empty set" >::
aec [1; 3] (CSet.union (CSet.of_list [1; 3]) (CSet.of_list []));
"union of non-empty sets contains all unique elements" >::
aec [3; 2; 1] (CSet.union (CSet.of_list [1; 3]) (CSet.of_list [2; 3]));
]
let () =
run_test_tt_main ("custom_set tests" >::: tests)
open Base
module type ELEMENT = sig
type t
val compare : t -> t -> int
end
module Make (El : ELEMENT) = struct
type t = (El.t, unit) Avltree.t
type el = El.t
let empty () = ref Avltree.empty
let is_empty = Avltree.is_empty
let is_member = Avltree.mem ~compare:El.compare
let add s value =
Avltree.add s ~key:value ~data:() ~compare:El.compare ~replace:true
~added:(ref false)
let of_list l =
let tree = empty () in
List.iter ~f:(fun item -> tree := add !tree item) l;
!tree
let to_list s =
let result = ref [] in
Avltree.iter ~f:(fun ~key ~data:_ -> result := key :: !result) s;
!result
let build_from ~cond s =
let result = empty () in
Avltree.iter
~f:(fun ~key ~data:_ -> if cond key then result := add !result key)
s;
!result
let difference s1 s2 = build_from ~cond:(Fn.non (is_member s2)) s1
let intersect s1 s2 = build_from ~cond:(is_member s2) s1
let is_disjoint s1 s2 =
if is_empty s1 && is_empty s2 then true else is_empty @@ intersect s1 s2
let equal s1 s2 =
let eq = ref true in
Avltree.iter
~f:(fun ~key ~data:_ -> if not (is_member s2 key) then eq := false)
s1;
Avltree.iter
~f:(fun ~key ~data:_ -> if not (is_member s1 key) then eq := false)
s2;
!eq
let is_subset s1 = Fn.compose (equal s1) (intersect s1)
type status = [ `OnlyA | `OnlyB | `Both ]
let diff_filter _ _ _ = failwith "'diff_filter' is missing"
let union s1 s2 =
let result = empty () in
let add_to_result ~key ~data:_ = result := add !result key in
Avltree.iter ~f:add_to_result s1;
Avltree.iter ~f:add_to_result s2;
!result
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.
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.
Sign up Learn More
Community comments