🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉
Avatar of stevejb71

stevejb71's solution

to Custom Set in the OCaml Track

Published at Jul 13 2018 · 5 comments
Instructions
Test suite
Solution

Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code 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 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

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 [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)
open Core.Std

module type ELEMENT = sig
  type t
  val compare : t -> t -> int
  val equal : t -> t -> bool
  val to_string : t -> string
end

type 'a node = {
  value: 'a;
  left: 'a bst;
  right: 'a bst;
}
and 'a bst = Empty | Node of 'a node

let singleton x = Node {value = x; left = Empty; right = Empty}

let (<<) f g x = f (g x)

module Make(El: ELEMENT) = struct
  type el = El.t
  type t = el bst

  let (<) (l: el) (r: el): bool = El.compare l r < 0
  let (=) = El.equal

  let empty = Empty

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

  let rec is_member x n = match x with
    | Node {value = v; _} when v = n -> true
    | Node {left = l; value = v; _} when n < v -> is_member l n
    | Node {right = r; _} -> is_member r n
    | _ -> false

  let rec equal a b = match (a, b) with
    | (Empty, Empty) -> true
    | (Node {left = l1; value = v1; right = r1}, Node {left = l2; value = v2; right = r2}) ->
        v1 = v2 && equal l1 l2 && equal r1 r2
    | _ -> false

  let rec add x n = match x with
    | Empty -> singleton n
    | Node {value = v; _} when n = v -> x
    | Node {left = l; value = v; right = r} when n < v ->
        Node {left = add l n; right = r; value = v}
    | Node {left = l; value = v; right = r} ->
        Node {left = l; right = add r n; value = v}

  let rec to_list = function
    | Empty -> []
    | Node {value = v; left = l; right = r} -> to_list l @ (v :: to_list r)

  let of_list_from init = List.fold ~init ~f:add

  let union x = of_list_from x << to_list

  let of_list = of_list_from empty

  let to_string x =
    let l = List.map ~f:El.to_string (to_list x) in
    sprintf "{%s}" (String.concat ~sep:" " l)

  let rec remove x n = match x with
    | Empty -> Empty
    | Node {left = l; value = v; right = r} when n = v -> (
        match (l, r) with
          | (Empty, _) -> r
          | (_, Empty) -> l
          | (Node {left = ll; value = vl; right = rl}, _) -> Node {left = remove ll n; value = vl; right = rl}
        )
    | Node {left = l; value = v; right = r} when n < v -> Node {left = remove l n; value = v; right = r}
    | Node {left = l; value = v; right = r} -> Node {left = l; value = v; right = remove r n}

  let difference x = List.fold ~init:x ~f:remove << to_list

  let intersect xs = List.fold ~init:empty ~f:(fun acc y -> if is_member xs y then add acc y else acc) << to_list
end

Community comments

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

Binary tree implementation. I've not made any attempt to balance the tree, something like https://en.wikipedia.org/wiki/Red%E2%80%93black_tree would be much better.

I've implemented is_member and is_empty rather than compare, as they are more useful operations on a set.

Avatar of bcc32

Nicely done. I don't know if I would have used a record for nodes, since it's not particularly easier to read and makes everything a bit messy.

If you do plan on trying to balance the tree, I would suggest you to also take a look at AVL trees. I have a hunch that they are easier to implement functionally, but I'm not entirely sure.

Avatar of hoichi

Live the remove function, especially this part:

match (l, r) with
    | (Empty, _) -> r
    | (_, Empty) -> l

(It’s probably obvious to an experienced FPer, but I still can’t get over the beauty of pattern matching.)

Also, funny how you’ve done difference with folding over a list, whereas I ended up implementing fold and filter (but not remove!) over the tree itself.

Avatar of stevejb71

@hoichi I think I was a bit lazy with difference. Your way sounds more efficient.

Avatar of hoichi

Oh well, my tree is not balanced in any way, so probably not that efficient too.

What can you learn from this solution?

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?