Set behaving inconsistently

#1

I found a subtle bug in production which is caused by comparing a sum type.

open Jest;

open ExpectJs;

type key =
  | KeyPID(int)
  | KeyVPID(int);

module KeyCmp =
  Belt.Id.MakeComparable({
    type t = key;
    let cmp: (key, key) => int =
      (a, b) =>
        switch (a, b) {
        | (KeyPID(x), KeyPID(y)) => compare(x, y)
        | (KeyVPID(x), KeyVPID(y)) => compare(x, y)
        | _ => 1
        };
  });

describe("OnpingStdLib_Compare", () => {
  test("test comparable module functor working with set", () => {
    let setA =
      Belt.Set.fromArray(
        [|
          KeyPID(123),
          KeyPID(456),
          KeyVPID(789),
          KeyVPID(910),
          KeyPID(555),
        |],
        ~id=(module KeyCmp),
      );

    let setB = Belt.Set.fromArray([|KeyVPID(789)|], ~id=(module KeyCmp));
    let intersection = Belt.Set.intersect(setA, setB);

    Js.log2("intersection", Belt.Set.toArray(intersection));

    intersection |> Belt.Set.isEmpty |> expect |> toBe(false);
  })
});

The intersection results in an empty set. Two distinct disjointed of a sum type are not equivalent and I’m not sure how I can write the proper MakeComparable to make this work. Setting it to -1 also caused the same bug (not for this particular Set, but a different set of keys).

#2

Try this compare function:

let cmp: (key, key) => int =
  (a, b) =>
    switch (a, b) {
    | (KeyPID(x), KeyPID(y)) => compare(x, y)
    | (KeyVPID(x), KeyVPID(y)) => compare(x, y)
    | (KeyVPID(_), KeyPID(_)) => 1
    | (KeyPID(_), KeyVPID(_)) => -1
    };

The last two cases ensure that KeyVPID is always “greater” than KeyPID, and your first two cases define ordering within a single tag. Together they define a “total order” which is a requirement for Comparable.