Data Structures in ReasonML: #3 Set

Set.re

/* Set */
/* Contains unique elements */
module type Ord = {
  type t;
  let eq: (t, t) => bool;
  let lt: (t, t) => bool;
  let leq: (t, t) => bool;
};

module Integer: Ord with type t = int = {
  type t = int;
  let eq = (===);
  let lt = (<);
  let leq = (<=);
};

module type Print = {type t; let toString: t => string;};

module PrintInteger: Print with type t = Integer.t = {
  type t = int;
  let toString = t => string_of_int(t);
};

module type Set = {
  type t;
  type set('t) = list((t, t));
  /* Create an empty Set */
  let empty: unit => set(t);
  /* Check if an element exists in given Set also implemented as ~mem */
  let contains: (t, set(t)) => bool;
  /* Inserts an element into a Set */
  let add: (t, set(t)) => set(t);
  /* Removes an element from a Set - if the element actually exists in given Set */
  let remove: (t, set(t)) => set(t);
  /* Size of Set also implemented as ~size */
  let length: set(t) => int;
  /* Union returns all unique elements for two given sets.
       i.e. [1, 3, 4, 9] and [3, 5, 7] => [1, 3, 4, 5, 7, 9]
     */
  let union: (set(t), set(t)) => set(t);
  /* Intersect returns all elements existing in both given sets. Also defined as ~inter.
       i.e. [1, 3, 4, 7, 9] and [3, 5, 7] => [3, 7]
     */
  let intersect: (set(t), set(t)) => set(t);
  /* Disjunct returns all elements that do not exist in both of the given sets.
     The inverse of intersect.
        i.e. [1, 3, 4, 7, 9] and [3, 5, 7] => [1, 4, 5, 9]
      */
  let disjunct: (set('t), set('t)) => set('t);
  /* Diff returns all elements in Set1 but not in Set2 */
  let diff: (set('t), set('t)) => set('t);
  let print: set('t) => string;
};

module MakeSet =
       (Elem: Ord, Print: Print with type t = Elem.t)
       : (Set with type t := Elem.t) => {
  type t = Elem.t;
  type set('t) = list((t, t));
  let empty = () => [];
  let contains = (e, s) => List.exists(((_k, v)) => Elem.eq(e, v), s);
  let add = (e, s) =>
    if (contains(e, s)) {
      s;
    } else {
      [(e, e), ...s];
    };
  let remove = (e, s) =>
    if (contains(e, s)) {
      List.remove_assoc(e, s);
    } else {
      s;
    };
  let length = s => List.length(s);
  let union = (set1, set2) => {
    let found = List.filter(((_k, v)) => ! contains(v, set1), set2);
    List.append(set1, found);
  };
  let intersect = (set1, set2) =>
    List.filter(((_k, v)) => contains(v, set2), set1);
  let disjunct = (set1, set2) => {
    let found1 = List.filter(((_k, v)) => ! contains(v, set2), set1);
    let found2 = List.filter(((_k, v)) => ! contains(v, set1), set2);
    List.append(found1, found2);
  };
  let diff = (set1, set2) =>
    List.filter(((_k, v)) => ! contains(v, set2), set1);
  let print = s => {
    let str = ref("");
    List.iter(((_k, v)) => str := str^ ++ " " ++ Print.toString(v), s);
    str^;
  };
};

let run = () => {
  module Set = MakeSet(Integer, PrintInteger);
  let t = Set.empty();
  let t = Set.add(1, t);
  let t = Set.add(2, t);
  let t = Set.add(4, t);
  let t = Set.add(4, t);
  let t = Set.add(5, t);
  let t = Set.add(4, t);
  Js.log2("Size: ", Set.length(t));
  Js.log2("Contains 4?", Set.contains(4, t));
  Js.log("Remove 4");
  let t = Set.remove(4, t);
  Js.log("Remove 3");
  let t = Set.remove(3, t);
  Js.log2("Contains 4?", Set.contains(4, t));
  Js.log2("Size: ", Set.length(t));
  Js.log("Create second set");
  let t2 =
    Set.empty() |> Set.add(1) |> Set.add(3) |> Set.add(5) |> Set.add(10);
  Js.log2("Size Set 2: ", Set.length(t2));
  let t3 = Set.union(t, t2);
  Js.log2("Set1: ", Set.print(t));
  Js.log2("Set2: ", Set.print(t2));
  Js.log2("Result of union(set1, set2): ", Set.print(t3));
  let t4 = Set.intersect(t, t2);
  Js.log2("Result of intersect(set1, set2): ", Set.print(t4));
  let t5 = Set.disjunct(t, t2);
  Js.log2("Result of disjunct(set1, set2): ", Set.print(t5));
  let t6 = Set.diff(t, t2);
  Js.log2("Result of diff(set1, set2): ", Set.print(t6));
};