🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉 # hoichi's solution

## to Custom Set in the OCaml Track

Published at Apr 05 2019 · 0 comments
Instructions
Test suite
Solution

#### Note:

This exercise has changed since this solution was written.

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.

## Getting Started

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

## Installation

To work on the exercises, you will need `Opam` and `Base`. 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 base:

``````opam install base
``````

To run the tests you will need `OUnit`. Install it using `opam`:

``````opam install ounit
``````

## Running Tests

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

``````make
``````

## Interactive Shell

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

## Feedback, Issues, Pull Requests

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!

## Submitting Incomplete Solutions

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

### test.ml

``````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 ));
"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 ));
"non-empty set is a not subset of an empty set">::
assert_false (CSet.is_subset (CSet.of_list ) (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 ));
"non-empty set is disjoint with empty set">::
assert_true (CSet.is_disjoint (CSet.of_list ) (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 ) (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 ) (CSet.union (CSet.of_list []) (CSet.of_list )));
"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)``````
``````module type COMPARABLE = sig
type t
val compare : t -> t -> int
end

module type CUSTOM_SET = sig
type elt
type t

val of_list : elt list -> t
val is_empty : t -> bool
val is_member : t -> elt -> bool
val is_subset : t -> t -> bool
val is_disjoint : t -> t -> bool
val equal : t -> t -> bool
val add : t -> elt -> t
val intersect : t -> t -> t
val difference : t -> t -> t
val union : t -> t -> t
end

module Make(Ord : COMPARABLE)
: (CUSTOM_SET with type elt = Ord.t) = struct
open Base

type elt = Ord.t
type t = Empty | Node of { l: t; r: t; v: elt }

(* HELPERS *)

let cmp = Ord.compare

let create l r v = Node { l; r; v; }

let empty = Empty

let new_node el = Node { l = Empty; r = Empty; v = el; }

(*  Using CPS for tail optimization (using heap instead of stack).
It’s not practical for the tests’ sizes, but what the heck.
Also, I should get to grokking the deeper suff some day:
https://stackoverflow.com/a/9323417/2658546
*)
let fold t ~f ~init =
let rec fold_ ~t ~init cont =
match t with
| Empty -> cont init
| Node {l; r; v} ->
let seed = f init v in
fold_ ~t:l ~init:seed (fun res_l ->
fold_ ~t:r ~init:res_l cont
)
in fold_ ~t ~init Fn.id

(* THE INTERFACE *)

(* That is not a balanced tree, but it’s my first, so どうぞ　よろしく *)
let rec add s el =
match s with
| Empty -> new_node el
| Node { l; r; v; } as t ->
let c = cmp el v in
if c < 0 then create (add l el) r v
else if c > 0 then create l (add r el) v
else t (* don’t add dupes to a set *)

let of_list = List.fold ~init:empty ~f:add

let is_empty = function
| Empty -> true
| _ -> false

let rec is_member s el =
match s with
| Empty -> false
| Node { l; r; v } ->
let c = cmp el v in
if c = 0 then true
else if c < 0 then is_member l el
else is_member r el

let is_subset t1 t2 =
fold t1 ~init:true ~f:(fun res el -> res && is_member t2 el)

let is_disjoint t1 t2 =
fold t1 ~init:true ~f:(fun res el -> res && not @@ is_member t2 el)

let equal t1 t2 = is_subset t1 t2 && is_subset t2 t1

let filter ~f:filter_f =
fold ~init:empty ~f:(fun acc el ->
if filter_f el then add acc el
else acc
)

let intersect t1 = filter ~f:(is_member t1)

let difference t1 t2 = filter t1 ~f:(Fn.non @@ is_member t2)

let union t1 = fold ~init:t1 ~f:add
end``````

## Community comments

Find this solution interesting? Ask the author a question to learn more.

### hoichi's Reflection

Did it with the basest, unbalanced tree. Also, most of the heavy lifting is done via the `fold` or `filter` helpers